Show all threads Hide all threads Show all messages Hide all messages | Page 3 | Very difficult solution (and some tests) | AleshinAndrei | 1111. Squares | 9 Jan 2022 18:33 | 2 | 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" | WA on #test 1 | abid1729 | 1111. Squares | 18 Aug 2019 01:04 | 1 | /****************************************************************************** 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; } | Solution | ANTON BL1K `~ | 1111. Squares | 3 Oct 2018 20:52 | 1 | The problem is rather easy, just compare squares due to rationality of numbers | To admins: the statement corrections | Fyodor Menshikov | 1111. Squares | 13 Aug 2018 23:16 | 1 | 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? | My AC. But i don't understand... | AleRD | 1111. Squares | 18 Nov 2012 02:29 | 1 | 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 ? | i think this test is like test #3 | BaJIuK | 1111. Squares | 15 Mar 2012 08:41 | 2 | 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. | Hint on WA#3 | Pong Eksombatchai | 1111. Squares | 26 Mar 2013 23:59 | 2 | 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 | help me to understant this problem | Arstanbek | 1111. Squares | 28 Jan 2011 10:18 | 1 | | answer plz | 72VanVector[SevNTU] | 1111. Squares | 18 Aug 2010 01:18 | 2 | 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. | got wa#3?? strange... | Ivan | 1111. Squares | 16 Aug 2010 04:19 | 1 | #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;} | Page 2 | Hint | ASK | 1111. Squares | 11 Feb 2011 15:29 | 2 | Hint ASK 24 Mar 2010 18:15 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). Re: Hint Phan Hoài Nam (Harvey Nash) 11 Feb 2011 15:29 Nice solution ! Edited by author 11.02.2011 15:53 | could anybody help me | Jet Li | 1111. Squares | 24 Oct 2009 15:46 | 1 | 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 | No subject | Jet Li | 1111. Squares | 24 Oct 2009 15:42 | 1 | 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 | Those who get WA#3,mind your sort!! | cloudygooose | 1111. Squares | 7 Jul 2009 20:05 | 1 | I got WA#3,after a day I suddenly found that my simple sort is not stable!!So MIND YOUR SORT!! | To ADMINS!!! Test #10 check it please! | Sasha Bar [TNU] | 1111. Squares | 31 Jan 2010 02:42 | 4 | 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. 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) | AC, no problem ;-) | Ilya Mitin (2) | 1111. Squares | 18 Aug 2019 11:48 | 3 | 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; } | If you WA 8, change epsilon | Liu Strong | 1111. Squares | 3 Aug 2013 11:53 | 4 | 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;) | If you have WA4 | DixonD (Lviv NU) | 1111. Squares | 23 Feb 2008 02:25 | 1 | Check is your sorting is stable | What is 3d test???? | M@STeR.SoBG | 1111. Squares | 6 Jan 2008 22:33 | 2 | Could anybody help me?? If u need i can post my code. i've found the bug in my program. i wrote wrong formula. Now the problem is accepted. Thnx for such a nice problem! P.S. sorry for my English :-)) | Oybek na gap | SoSimple | 1111. Squares | 12 Jan 2012 18:17 | 7 | 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 .... |
|
|