ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1111. Квадраты

Li Ruizhe Why my program got WA? [15] // Задача 1111. Квадраты 25 июн 2002 19:58
It's my program:

{$N+}
Program p1111;

Type
  TPoint=Record
           x,y:Double;
         End;

Var
  Point:Array[1..100,1..2] Of TPoint;
  Len:Array[1..100] Of Double;
  num:Array[1..100] Of Integer;
  n:Integer;
  po:TPoint;

  Procedure Other(p1,p2:TPoint;Var p3,p4:TPoint);
  Var m,n:Double;
      po:TPoint;
  Begin
    po.x:=(p1.x+p2.x)/2;
    po.y:=(p1.y+p2.y)/2;
    n:=p1.x-po.x;m:=p1.y-po.y;
    p3.x:=m;p3.y:=-n;
    p4.x:=-p3.x;p4.y:=n;
    p3.x:=p3.x+po.x;p3.y:=p3.y+po.y;
    p4.x:=p4.x+po.x;p4.y:=p4.y+po.y;
  End;

  Procedure Init;
  Var
    i:Integer;
  Begin
    {$IFNDEF ONLINE_JUDGE}
    Assign(Input,'1111.Txt');
    Reset(Input);
    {$ENDIF}
    Readln(n);
    For i:=1 To n Do
      Readln(Point[i,1].x,Point[i,1].y,
             Point[i,2].x,Point[i,2].y);
    Readln(po.x,po.y);
  End;

  Procedure Main;
  Var
    i,j,k:Integer;
    p:Array[1..5] Of TPoint;
    u,A,B,C,L1,L2,L3,q1,q2,S:Double;
  Begin
    For i:=1 To n Do
    Begin
      num[i]:=i;
      p[1]:=Point[i,1];
      p[3]:=Point[i,2];
      Other(p[1],p[3],p[2],p[4]);
      p[5]:=p[1];
      L1:=sqr(p[1].x-p[2].x)+sqr(p[1].y-p[2].y);
      If Abs(L1)<1e-14
      Then Begin
             Len[i]:=sqr(po.x-p[1].x)+sqr(po.y-p[1].y);
             Continue;
           End;
      S:=0;
      For j:=1 To 4 Do
      Begin
        q1:=sqrt(sqr(po.x-p[j].x)+sqr(po.y-p[j].y));
        q2:=sqrt(sqr(po.x-p[j+1].x)+sqr(po.y-p[j+1].y));
        u:=(q1+q2+sqrt(L1))/2;
        S:=S+sqrt(u*(u-q1)*(u-q2)*(u-sqrt(L1)));
      End;
      If Abs(S-L1)<1e-14
      Then Begin
             Len[i]:=0;
             Continue;
           End;
      S:=1e300;
      For j:=1 To 4 Do
      Begin
        A:=p[j+1].y-p[j].y;
        B:=p[j].x-p[j+1].x;
        C:=-A*p[j].x-B*p[j].y;
        L2:=sqr(p[j].x-po.x)+sqr(p[j].y-po.y);
        L3:=sqr(p[j+1].x-po.x)+sqr(p[j+1].y-po.y);
        If not((L1+L3-L2<0)or(L1+L2-L3<0))
        Then Begin
               u:=Sqr(A*po.x+B*po.y+C)/(A*A+B*B);
               If u<S
               Then S:=u;
             End;
      End;
      For j:=1 To 4 Do
      Begin
        u:=Sqr(po.x-p[j].x)+Sqr(po.y-p[j].y);
        If u<S
        Then S:=u;
      End;
      Len[i]:=S;
    End;
    For i:=1 To n-1 Do
      For j:=i+1 To n Do
      If Len[i]>Len[j]
      Then Begin
             S:=Len[i];
             Len[i]:=Len[j];
             Len[j]:=s;
             k:=num[i];
             num[i]:=num[j];
             num[j]:=k;
           End;
    For i:=1 To n-1 Do
      Write(num[i],' ');
    Writeln(num[n]);
  End;

Begin
  Init;
  Main;
End.
shitty.Mishka Try this test (+) [14] // Задача 1111. Квадраты 26 июн 2002 14:44
12
-797 -6314 -2827 9400
6599 8354 -1698 -9262
-4367 4707 -6819 -3456
-9081 -1597 -2034 -8071
-5344 -1294 5374 7391
8886 -1433 8797 8123
5755 4629 6117 1844
-9568 -9375 413 -8893
6399 2576 -235 1017
-2189 9272 3306 -1693
8554 -3590 5752 2674
2770 7881 -2439 -3635
2627 2931

 the answer of my program is

1 2 5 9 10 12 6 7 11 3 4 8
Koala Why is No.1 the first? // Задача 1111. Квадраты 26 июл 2002 19:26
This is my answer:
2 5 10 12 9 7 11 1 6 4 3 8
The particular answers of my program:

The distance of point 1 is: 0.0
The distance of point 2 is: 3758.8820637
The distance of point 3 is: 5317.7131577
The distance of point 4 is: 6516.753678
The distance of point 5 is: 2267.2803272
The distance of point 6 is: 1483.260766
The distance of point 7 is: 1920.5396377
The distance of point 8 is: 10242.585389
The distance of point 9 is: 1425.1471184
The distance of point 10 is:2102.5891829
The distance of point 11 is:3011.0680172
The distance of point 12 is:1880.3884245

I wonder if I'm wrong, could anybody tell me please?
Tim Green Re: Try this test (+) [7] // Задача 1111. Квадраты 24 окт 2004 08:18
my out is this
1: 0.000000
2: 0.000000
3: 5317.713158
4: 6516.753678
5: 0.000000
6: 1483.260766
7: 1920.539638
8: 10242.585389
9: 0.000000
10: 0.000000
11: 3011.068017
12: 0.000000
adove is for debug!
1 2 5 9 10 12 6 7 11 3 4 8

but i still wrong answer 3
Xeno Re: Try this test (+) [4] // Задача 1111. Квадраты 28 окт 2004 15:14
#3 ERROR
ALL THE SAME

1: 0.000000
2: 0.000000
3: 5317.713158
4: 6516.753678
5: 0.000000
6: 1483.260766
7: 1920.539638
8: 10242.585389
9: 0.000000
10: 0.000000
11: 3011.068017
12: 0.000000

1 2 5 9 10 12 6 7 11 3 4 8
Junk Re: Try this test (+) [3] // Задача 1111. Квадраты 10 авг 2009 17:22
right answer for test

12
-797 -6314 -2827 9400
6599 8354 -1698 -9262
-4367 4707 -6819 -3456
-9081 -1597 -2034 -8071
-5344 -1294 5374 7391
8886 -1433 8797 8123
5755 4629 6117 1844
-9568 -9375 413 -8893
6399 2576 -235 1017
-2189 9272 3306 -1693
8554 -3590 5752 2674
2770 7881 -2439 -3635
2627 2931

is

#1: 0.000000000
#2: 0.000000000
#3: 5317.713157659
#4: 6516.753678021
#5: 0.000000000
#6: 1483.260766015
#7: 1920.539637706
#8: 10242.585388968
#9: 0.000000000
#10: 0.000000000
#11: 3011.068017185
#12: 0.000000000

1 2 5 9 10 12 6 7 11 3 4 8
Rohil Sinha Re: Try this test (+) [1] // Задача 1111. Квадраты 9 окт 2010 22:32
But these coordinates do not specify a square. Taking the 1st test case, how is (-797,-6314) (-2827,9400) opposite vertexes of a square ?
Ilya Re: Try this test (+) // Задача 1111. Квадраты 29 апр 2011 20:12
The sides of square may be not parallel to the axes.
Vadim Re: Try this test (+) // Задача 1111. Квадраты 6 ноя 2011 01:46
Why 1) 0.000000000?
Boris Strandjev Thanks guys! [1] // Задача 1111. Квадраты 19 окт 2007 19:08
The test and the results were quite helpful I also managed to debug my problem with them thanks guys! And also an interesting thing is that my mistake is so stupid that no one else could have done it and still I failed the 3rd test. So I think it is quite complicated and just caches all possible bugs(as I looked trough the results of the submits only one managed to fail a test with higher number). Here is an another task try to pass the 3rd and still fail a test.
данные Re: Thanks guys! // Задача 1111. Квадраты 16 дек 2008 12:51
If you wa 3
please check your sort algorithm!
LeXuS[Alex Kalugin] To shitty.Mishka: [1] // Задача 1111. Квадраты 24 окт 2004 22:33
Ты не мог бы помоч мне решить задачу №1028?
Расказать способы решения за логарифмическое время...
Мой е-мэйл: lexus_ua@list.ru

Спасибо.
Michael Rybak (accepted@ukr.net) I've sent you some hints on logarithmic solution of 1028 (+) // Задача 1111. Квадраты 26 окт 2004 21:12
Please use english, it is a common rule here.

BTW, in case you don't know this - shitty.Mishka is my former login here.

Edited by author 26.10.2004 21:13

Edited by author 26.10.2004 21:14
198808xc Thanks. [1] // Задача 1111. Квадраты 25 июн 2005 15:44
Thanks very much for helping me.
With the help of this Testcase, I got ACed.

PS: To all persons who haven't got ACed yet:
  Pay Attention to the Precision, please...
  Only 1e-14 is Enough.
  Otherwise you will be wrong.
  And, the most important one hint is:
    when you calculate the Side Length of a Square,
    your Precision would be only Sqrt(1e-14)=1e-7,
    that would work!!!

I hope that my hint can help some people.
At last, sorry for my poor English(I am Chinese).
Good luck!
AXIS About Eps // Задача 1111. Квадраты 13 янв 2007 17:07
My program is quite complexive,
it works with any rectangle, not only a square.

And the most interesting feature - i haven't used epsilon at all!

That means, in this problem precision of extended type in
Pascal is enough to solve it