A could do the simple solution there I have 4 points of square and simple calculations of dist to this square. But i found this very easy and i figure out difficult formula for equations of the lines which bounding this square. I calculates dist for this lines and analyzing them. This is initialization of square: /* void init(Point p1, Point p2){ int64_t dx = p1.x-p2.x, dy = p1.y-p2.y; a = dx + dy; // some coof for line-equation b = dx - dy; c1 = dx*(p1.x-p1.y) + dy*(p1.x+p1.y); c2 = dy*(p2.x-p2.y) - dx*(p2.x+p2.y); dc = dx*dx + dy*dy; // delta between c-coof two parallel lines if (dc == 0) { // if square is dot c1 = p1.x; c2 = p1.y; } } */ There i calculate dists to lines /* if (dc == 0){ return std::hypot((p0.x - c1), (p0.y - c2)); } else { double d1 = (b*(p0.y) - a*(p0.x) + c1)/sqrt(2*dc), // signed dist to first line d2 = (b*(p0.x) + a*(p0.y) + c2)/sqrt(2*dc), // signed dist to perpendicular to first line d = sqrt(dc/2.0); // delta between two parallel lines (a side of square) ...... */ "d" always is positive (if square isn't dot), bcs "(d1 - d) < d1" (dist to nearest line less than dist to farthest line) there is some conditionals for calculate the dist to square /* if (d1 < 0) { if (d2 < 0) { // 1 corner x1 = (c1*a - c2*b)/(2.0*dc), y1 = (-c1*b - c2*a)/(2.0*dc) } else if(d2 <= d){ // 1 side return fabs(d1); } else { // 2 corner x2 = (c1*a - c2*b)/(2.0*dc) + (b/2.0), y2 = (-c1*b - c2*a)/(2.0*dc) + (a/2.0) } } else if (d1 <= d) { if (d2 < 0){ // 2 side return fabs(d2); } else if(d2 <= d){ // inside square return 0; } else { // 3 side return fabs(d2 - d); } } else { if (d2 < 0){ // 3 corner x3 = (c1*a - c2*b)/(2.0*dc) - (a/2.0), y3 = (-c1*b - c2*a)/(2.0*dc) + (b/2.0) } else if(d2 <= d){ // 4 side return fabs(d1 - d); } else { // 4 corner x4 = (c1*a-c2*b)/(2.0*dc) + (b-a)/2.0, y4 = (p0.y + (c1*b+c2*a)/(2.0*dc) + (a+b)/2.0 } } */ after this we sorting dist with num, and print the answer tests: 8 0 0 2 2 2 4 0 6 -8 -3 -8 -7 7 11 4 15 5 -5 9 -6 -2 -2 -2 -4 -4 6 -8 10 6 6 10 6 ..... 6 2 : ans is "8 1 2 5 6 4 7 3" 0 0 : ans is "1 6 2 5 7 3 8 4" Edited by author 26.08.2020 02:41 I got acc but for test case "0 0" it's not "1 6 2 5 7 3 8 4" and i got "1 8 6 2 5 7 3 4" my code passed yours test but shows WA1 #include <bits/stdc++.h> using namespace std; int main() { int N,a[55],b[55],i,c[55],j,d[55],t,e[55],m,n; unsigned long long x,y,p,arr[55]; cin>>N; for(i=0;i<N;i++){ cin>>a[i]>>b[i]>>c[i]>>d[i]; e[i]=i; } cin>>m>>n; for(i=0;i<N;i++){ x=max(a[i]-m,m-c[i]); if(x<0){ x=0; } y=max(b[i]-n,n-d[i]); if(y<0){ y=0; } arr[i]=x*x+y*y; } for(i=0;i<N;i++){ for(j=i+1;j<N;j++){ if(arr[i]>a[j]){ p=arr[i]; arr[i]=arr[j]; arr[j]=p; t=e[i]; e[i]=e[j]; e[j]=t; } } } for(i=0;i<N;i++){ cout<<e[i]+1<<" "; } return 0; } /****************************************************************************** Online C++ Compiler. Code, Compile, Run and Debug C++ program online. Write your code in this editor and press "Run" button to compile and execute it. *******************************************************************************/ #include <bits/stdc++.h> using namespace std; int main() { int N,a[55],b[55],i,c[55],j,d[55],e[55],m,n; unsigned long long x,y,arr[55]; cin>>N; for(i=0;i<N;i++){ cin>>a[i]>>b[i]>>c[i]>>d[i]; e[i]=i; } cin>>m>>n; for(i=0;i<N;i++){ x=max(a[i]-m,m-c[i]); if(x<0){ x=0; } y=max(b[i]-n,n-d[i]); if(y<0){ y=0; } arr[i]=x*x+y*y; } for(i=0;i<N;i++){ for(j=i+1;j<N;j++){ if(arr[i]>a[j]){ arr[i]=arr[j]; e[i]=e[j]; } } } for(i=0;i<N;i++){ cout<<e[i]+1<<endl; } return 0; } The problem is rather easy, just compare squares due to rationality of numbers Could you specify in the problem statement that the coordinates of the point in the last line are integer? Also, could you specify the kind of precision near 10^{-14}? Is it absolute or relative? To those who WA 8: Try to change your epsilon to something else then 1e-14. I changed that to 1e-8 and then I got AC. Also, don't calculate S△ABC as 0.5*AB*AC! It should be 0.5*AB*AC*sin∠A As I see - your advice is to use greater epsilon. May be it is better to avoid dangerous computations? I've solved this problem in integers - so all comparations were EXACT =) So, I think, the note about precision in problem text is superfluous. How did you solved it? My first solution was with integers but than i noticed not all squares are axes aligned. :( Anyway, could you send me you solution? My email is marshal at mail.bg. Thank you! I got AC without epsilon;) When you compare in the sort, try using epsilon = 1e-8. When I used 1e-13, I keep getting WA#3. I didn't understand that squares could be rotated. My solution works with both EPS = 1e-7 and 1e-14. Edited by author 26.03.2013 23:59 I have found two other points of square by this formula xc = (x1 + x3) / 2.0; yc = (y1 + y3) / 2.0; dx = (x3 - x1) / 2.0; dy = (y3 - y1) / 2.0; x2 = xc - dy; y2 = yc + dx; x4 = xc + dy; y4 = yc - dx; But i could not understood why this works. Then I use vector product to determine position of point etc. Can someone explain me ? 5 0 1 0 1 0 1 0 1 0 1 0 1 -9999 -9999 9999 -9999 -9999 9999 9999 9999 0 0 answer is 4 5 1 2 3 5 0 1 0 1 0 1 0 1 0 1 0 1 -9999 9999 9999 9999 -9999 -9999 9999 -9999 0 0 answer is 4 5 1 2 3 Good luck! Write a program that will sort the squares in ascending order according the distance from P. Edited by author 28.10.2007 14:24 Ishlayapti musobaqa boshlanganiga 20 min bo'ldi kirib ko'r Sani kurmin duribman Aniq bilaman dostupni olib tashladingmi yo bunday bo`lishi mumkin emas sen meni ko`rayapsan men esa yoq yana bir marta tekshirib ko`r Edited by author 28.10.2007 14:26 Edited by author 28.10.2007 14:43 Dostub bargan papkanga kir shunda go'rasan ishlab durganini Iltimos Timusni chat qivormela endi .... 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. 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 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? 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 #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 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 But these coordinates do not specify a square. Taking the 1st test case, how is (-797,-6314) (-2827,9400) opposite vertexes of a square ? The sides of square may be not parallel to the axes. 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. If you wa 3 please check your sort algorithm! Ты не мог бы помоч мне решить задачу №1028? Расказать способы решения за логарифмическое время... Мой е-мэйл: lexus_ua@list.ru Спасибо. 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 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! 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 To calculate the distance, rotate the square and the point so that the diagonal (if it is not a zero vector) becomes parallel to (1,1). In this case sides of the square are parallel to axes and the distance is trivial to calculate. The problem can be solved without floating point operations: the square of the distance is a rational number. But note that to compare (an/ad < bn/bd) you cannot use (an*bd < bn*ad) since the products can overflow 64-bit integers. Instead first compare the integer parts, and in case they are equal to the same number, subtract this number from both parts and compare the results using multiplication (denominators are 32-bit integers). Nice solution ! Edited by author 11.02.2011 15:53 what would be the distance between point (0,0) and square (1,0) (-1,0)?? Is it equal 0 or 0.7?? "If P is inside the square then the distance is zero" So, the distance is 0. #include <stdio.h> #include <math.h> #define M_PI_4 0.785398163397448309616 double d[51] = {0}; char printed[51] = {0}; struct point { double x; double y; }; struct square { point a; point b; } squares[51]; point rotate(point a, double d_al){ point _a; _a.x = a.x * cos(d_al) - a.y * sin(d_al); _a.y = a.x * sin(d_al) + a.y * cos(d_al); return _a; } double get_d(point a, point p) { return sqrt((double)((a.x - p.x)*(a.x-p.x) + (a.y -p.y)*(a.y - p.y))); } int main () { int n; scanf("%d",&n); point p; int i; for (i=1;i<=n;i++) { scanf("%lf%lf%lf%lf", &squares[i].a.x,&squares[i].a.y,&squares[i].b.x,&squares[i].b.y); } scanf("%lf%lf", &p.x,&p.y); double tn; double alpha,d_al; point _a,_b,_p,a,b,temp; for(i=1;i<=n;i++) { b = squares[i].b; a = squares[i].a; if(a.x == b.x && a.y == b.y) { d[i] = get_d(p,a); continue; } tn = (double)(b.y - a.y)/(double)(b.x - a.x); alpha = atan(tn); d_al = M_PI_4 - alpha; _a = rotate(a,d_al); _b = rotate(b,d_al); _p = rotate(p,d_al); if( _a.x > _b.x) { temp = _b; _b = _a; _a = temp; } if(_p.y > _b.y) { if(_p.x < _a.x) { temp.x = _a.x; temp.y = _b.y; d[i] = get_d(_p,temp); continue; } if(_p.x > _b.x) { d[i] = get_d(_p,_b); continue; } d[i] = _p.y - _b.y; continue; } if(_p.y < _a.y) { if(_p.x > _b.x) { temp.x = _b.x; temp.y = _a.y; d[i] = get_d(_p,temp); continue; } if(_p.x < _a.x) { d[i] = get_d(_p,_a); continue; } d[i] = _a.y - _p.y; continue; } if(_p.x < _a.x) { d[i] = _a.x - _p.x; continue; } if(_p.x > _b.x) { d[i] = _p.x - _b.x; continue; } d[i] = 0; } double min; int j,k; for(i=1;i<=n;i++) { min = 99999999999999999; k = 0; for(j=1;j<=n;j++) if(!printed[j] && min > d[j]) { min = d[j]; k = j; } printed[k] = 1; printf("%d ", k); } return 0;} Is test 10 correct? A couple old AC solutions now have WA 10, and my new solution too. Edited by author 29.04.2009 21:16 Test 10 is correct, but because of server error all AC solutions since April,14,2009 have received verdict WA#10. Now this error is fixed and all these submits are rejudged. Great, i got AC now :D I had Crash on test #10. In this test, point P coincides with some vertex of some square. (i had division by zero it this test) can anyone send me right algorith to this problem with AC code? I tried many times to solve but i couldn't. my e-mail is shohruhhon1@mail.ru why i'm getting WA2? here is my code program acm_1111_1; label W; const Eps=1e-15; type Square=record X1,Y1,X3,Y3:real; X2,Y2,X4,Y4:real; end; type Point=record X,Y:real; end; var p:array[1..100] of Square; Dis:array[1..100] of real; ID:array[1..100] of integer; Q,O:Point; r,sd1,sd2,sd3,sd4,vd1,vd2,vd3,vd4:real; Dist:real; i,j,kk,n:integer; function L1_2(i:integer; A:Point; B:Point):real; var a1,b1:real; begin a1:=p[i].X2-p[i].X1; b1:=p[i].Y2-p[i].Y1; L1_2:=a1*(B.X-A.X)-b1*(B.Y-A.Y); end; function L1_4(i:integer; A:Point; B:Point):real; var a1,b1:real; begin a1:=p[i].X4-p[i].X1; b1:=p[i].Y4-p[i].Y1; L1_4:=a1*(B.X-A.X)-b1*(B.Y-A.Y); end; function min(aa,bb,cc,dd:real):real; var mn:real; begin mn:=aa; if bb<mn then mn:=aa; if cc<mn then mn:=cc; if dd<mn then mn:=dd; min:=mn; end; begin read(n); for i:=1 to n do begin read(p[i].X1,p[i].Y1,p[i].X3,p[i].Y3); O.X:=(p[i].X1+p[i].X3)/2; O.Y:=(p[i].Y1+p[i].Y3)/2; r:=sqrt(sqr(p[i].X1-p[i].X3)+sqr(p[i].Y1-p[i].Y3))/2; p[i].X2:=-(p[i].Y1-p[i].Y3)/2+O.X; p[i].Y2:=(p[i].X1-p[i].X3)/2+O.Y; p[i].X4:=(p[i].Y1-p[i].Y3)/2+O.X; p[i].Y4:=-(p[i].X1-p[i].X3)/2+O.Y; end; read(Q.X,Q.Y); for i:=1 to n do begin r:=sqrt(sqr(p[i].X1-p[i].X2)+sqr(p[i].Y1-p[i].Y2)); vd1:=sqrt(sqr(Q.X-p[i].X1)+sqr(Q.Y-p[i].Y1)); vd2:=sqrt(sqr(Q.X-p[i].X2)+sqr(Q.Y-p[i].Y2)); vd3:=sqrt(sqr(Q.X-p[i].X3)+sqr(Q.Y-p[i].Y3)); vd4:=sqrt(sqr(Q.X-p[i].X4)+sqr(Q.Y-p[i].Y4)); O.X:=p[i].X1; O.Y:=p[i].Y1; sd1:=abs(L1_4(i,Q,O))/r; sd2:=abs(L1_2(i,Q,O))/r; O.X:=p[i].X3; O.Y:=p[i].Y3; sd3:=abs(L1_4(i,O,Q))/r; sd4:=abs(L1_2(i,O,Q))/r; if (abs(sd1)<Eps) or (abs(sd2)<Eps) or (abs(sd3)<Eps) or (abs(sd4)<Eps) then begin Dist:=min(vd1,vd2,vd3,vd4); goto W; end; if abs(sd1+sd3-r)<Eps then begin if abs(sd2+sd4-r)<Eps then begin Dist:=0; end; if abs(sd2-sd4-r)<Eps then begin Dist:=sd4; end; if abs(-sd2+sd4-r)<Eps then begin Dist:=sd2; end; end; if abs(sd1-sd3-r)<Eps then begin if abs(sd2+sd4-r)<Eps then begin Dist:=sd3; end; if abs(sd2-sd4-r)<Eps then begin Dist:=sd2; end; if abs(-sd2+sd4-r)<Eps then begin Dist:=vd2; end; end; if abs(-sd1+sd3-r)<Eps then begin if abs(sd2+sd4-r)<Eps then begin Dist:=sd1; end; if abs(sd2-sd4-r)<Eps then begin Dist:=vd4; end; if abs(-sd2+sd4-r)<Eps then begin Dist:=vd1; end; end; W: Dis[i]:=abs(Dist); ID[i]:=i; end; for i:=1 to n-1 do for j:=i+1 to n do begin if Eps<Dis[i]-Dis[j] then begin Dist:=Dis[i]; Dis[i]:=Dis[j]; Dis[j]:=Dist; kk:=ID[i]; ID[i]:=ID[j]; ID[j]:=kk; end; if abs(Dis[i]-Dis[j])<=Eps then if ID[i]>ID[j] then begin kk:=ID[i]; ID[i]:=ID[j]; ID[j]:=kk; end; end; for i:=1 to n do write(ID[i],' '); writeln; end. I'm not seeing any disadvantages..... Can you help me. Thanks in advance I got WA#3,after a day I suddenly found that my simple sort is not stable!!So MIND YOUR SORT!! Check is your sorting is stable |
|