First I got WA#22 while I used double than I change to use longdouble instead of double and I got WA#24 After that I change floor(x)/ceil(x) to floor(x+esp)/ceil(x-esp) and I got WA#24 too But when I try to use double again I got AC! [It's strange,too strange.I hate Accuracy issues] (Sorry for my poor English XP) Edited by author 07.09.2021 16:36 Test 01: 10 15 15 10 13 14 Ans 01: 25 Test 02: 0 5 5 0 1 1 Ans 02: 36 Test 03: 10 15 13 14 15 10 Ans 03: 100 Test 04: 10 15 13 14 15 10 Ans 04: 100 Test 05: 10 15 13 14 15 10 Ans 05: 100 Test 06: 2 1 1 2 1 1 Ans 06: 4 Test 07: 200 200 200 300 300 200 Ans 07: 17182 Test 08: 300 300 301 301 500 101 Ans 08: 80089 Test 09: 400 400 400 410 700 405 Ans 09: 90600 Test 10: 11 16 14 11 13 14 Ans 10: 15 Test 11: 4 1 1 6 2 2 Ans 11: 20 Test 12: 11 13 14 19 12 16 Ans 12: 18 Test 13: 11 14 14 20 12 18 Ans 13: 24 Test 14: 100 110 110 100 108 106 Ans 14: 100 Test 15: 100 110 90 100 94 108 Ans 15: 100 Test 16: Ans 16: Test 17: Ans 17: Test 18: Ans 18: Test 19: Ans 19: Test 20: Ans 20: Test 21: Ans 21: Test 22: Ans 22: Test 23: Ans 23: Test 24: Ans 24: Test 25: Ans 25: Test 26: Ans 26: Test 27: Ans 27: Test 28: Ans 28: Test 29: Ans 29: Test 30: Ans 30: Test 31: Ans 31: Test 32: Ans 32: Test 33: 1 -1000 -1 -1000 999 0 Ans 33: 3998000 Test 34: Ans 34: Test 35: 1 1 11 -1 2 0 Ans 35: 30 Test 36: -200 100 -300 -200 -195 -2 Ans 36: 32400 Test 37: -10 -5 -5 -10 -5 -100 Ans 37: 18496 Where the people find these tests? Edited by author 27.07.2007 01:01 Edited by author 27.07.2007 01:01 khmm. I don't know, what kind of cheat did you use, but it was very useful help. After some manipulations with precision, finally AC! Thank you Edited by author 17.08.2008 01:05 Thanks a lot! I didn't think about tests where some parts of circumstance could lie beyond the sqare[-1000, 1000]. Why test2 has answer 36? it seems that correct answer is 25. Yes, answer is correct. Center - 3.83333 3.83333 radius - 4.00694 x_min ~ -0.173605 < 0 y_min ~-0.173605 < 0 S = 36 I suspect rounding errors or something I have WA#9 too. The program seems to be right. Who can help me? I think, that your calculations not so are exact, as that is demanded with a problem. Try to not use intermediate values (for example radius etc.). you have all tests on timustests.4t.com Thank you very much. You were right about my bug. I have just change in my C++ code ceil(x) to ceil(x-eps) and floor(x) to floor(x+eps) and got AC!
Hey, UNKNOWN_LAMER! Do I know you from somewhere? je Edited by author 11.02.2018 04:58 This is a very simple problem. This is a simple school geometry. Please, give any hint how to improve my solution to get AC! Edited: Oh, i found bug and got AC! The bug was lower_boundary=1e-20 instead of lower_boundary=-1e20... seems like first test with negative boundaries is test #36 Edited by author 11.07.2011 18:53 i got the tests, send me a mail to ste_fanus@k.ro if you want them Input #1 10 15 15 10 13 14 Output #1 25 Input #2 0 5 5 0 1 1 Output #2 36 Input #3 10 15 13 14 15 10 Output #3,#4,#5 100 I don't understand test No 2. If starting and ending points of arc is (0,5) and (5,0), then co-ordinates of rectangle should be (0,0) and (5,5) right ? Hence area should be 25. Did I not understand the question correctly ? Please explain to me. (I'm an English BEGINNER...) First I used double and got WA on #9 Then I changed double to float and got WA on #42 At last I used double,and checked if it's #9(I've found the data of #9),and got AC... I was confused... Simply use angles comparison method and You'll get AC! How? What's that algorithm For all brute force solvers: it's enough to provide 1E-4 precision to AC :)) Very true!!! > Posted by SkorKNURE October 12, 2008 02:36 > > For all brute force solvers: it's enough to provide 1E-4 > precision to AC :)) Edited by author 29.03.2010 07:19 Edited by author 29.03.2010 07:19 Cause I'm lazy, I used fmin(double,double) and fmax in math.h directly. It went on well on my computer with MinGW. However, I always got WA1 here! At last, I tried to replace them with my own min function, that works! I don't know why, cause fmin and fmax are defined in ISO99 standard. But anyway I suggest all C/C++ users avoid using them. New tests were added. AC verdicts of 93 authors turned to WA. How i can get my old solutions?) It's impossible? I had problem with HD and lose all solutions) sorry, for my english :) I've submitted my AC solution for ten times... When it use function "hypot(x, y)" from math.h, it gets WA,1 If I change "hypot" to sqrt(x*x + y*y), it gets AC. =( Hm! #include<stdio.h> #include<math.h> double x0,q0,x1,q1,x2,q2,a,b,c,a0,b0,c0,a1,b1,c1,cx,cq,r,minx,maxx,minq,maxq; double roundup(double num) { if((long)(num)==num)return num; else if(num>0)return(long)(num+1);else return(long)(num); } double rounddown(double num) { if((long)(num)==num)return num; else if(num>0)return(long)(num);else return(long)(num-1); } int main() { scanf("%lf%lf%lf%lf%lf%lf",&x0,&q0,&x1,&q1,&x2,&q2); minx=x0;if(minx>x1)minx=x1; maxx=x0;if(maxx<x1)maxx=x1; minq=q0;if(minq>q1)minq=q1; maxq=q0;if(maxq<q1)maxq=q1; cx=(x0+x1)/2;cq=(q0+q1)/2; a=q1-q0;b=x0-x1;c=x1*q0-x0*q1; if(a!=0){a0=b/a;b0=-1;c0=cq-a0*cx;} else{a0=1;b0=0;c0=-cx;} cx=(x0+x2)/2;cq=(q0+q2)/2; a=q2-q0;b=x0-x2;c=x2*q0-x0*q2; if(a!=0){a1=b/a;b1=-1;c1=cq-a1*cx;} else{a1=1;b1=0;c1=-cx;} cx=(b0*c1-b1*c0)/(a0*b1-a1*b0);cq=(a1*c0-a0*c1)/(a0*b1-a1*b0); r=sqrt((x0-cx)*(x0-cx)+(q0-cq)*(q0-cq)); a=q1-q0;b=x0-x1;c=x1*q0-x0*q1; if((a*x2+b*q2+c)*(a*(cx-r)+b*cq+c)>=0)minx=cx-r; if((a*x2+b*q2+c)*(a*(cx+r)+b*cq+c)>=0)maxx=cx+r; if((a*x2+b*q2+c)*(a*cx+b*(cq-r)+c)>=0)minq=cq-r; if((a*x2+b*q2+c)*(a*cx+b*(cq+r)+c)>=0)maxq=cq+r; minx=roundup(minx); maxx=rounddown(maxx); minq=roundup(minq); maxq=rounddown(maxq); if(minx<-1000)minx=-1000;if(minq<-1000)minq=-1000; if(maxx>1000)maxx=1000;if(maxq>1000)maxq=1000; printf("%0.0lf",fabs((maxx-minx)*(maxq-minq))); return 0; } > #include<stdio.h> > #include<math.h> > > double > x0,q0,x1,q1,x2,q2,a,b,c,a0,b0,c0,a1,b1,c1,cx,cq,r,minx,maxx,minq,maxq; > > double roundup(double num) > { > if((long)(num)==num)return num; > else if(num>0)return(long)(num+1);else return(long)(num); > } > > double rounddown(double num) > { > if((long)(num)==num)return num; > else if(num>0)return(long)(num);else return(long)(num-1); > } > > int main() > { > scanf("%lf%lf%lf%lf%lf%lf",&x0,&q0,&x1,&q1,&x2,&q2); > minx=x0;if(minx>x1)minx=x1; > maxx=x0;if(maxx<x1)maxx=x1; > minq=q0;if(minq>q1)minq=q1; > maxq=q0;if(maxq<q1)maxq=q1; > cx=(x0+x1)/2;cq=(q0+q1)/2; > a=q1-q0;b=x0-x1;c=x1*q0-x0*q1; > if(a!=0){a0=b/a;b0=-1;c0=cq-a0*cx;} > else{a0=1;b0=0;c0=-cx;} > cx=(x0+x2)/2;cq=(q0+q2)/2; > a=q2-q0;b=x0-x2;c=x2*q0-x0*q2; > if(a!=0){a1=b/a;b1=-1;c1=cq-a1*cx;} > else{a1=1;b1=0;c1=-cx;} > cx=(b0*c1-b1*c0)/(a0*b1-a1*b0);cq=(a1*c0-a0*c1)/(a0*b1-a1*b0); > r=sqrt((x0-cx)*(x0-cx)+(q0-cq)*(q0-cq)); > a=q1-q0;b=x0-x1;c=x1*q0-x0*q1; > if((a*x2+b*q2+c)*(a*(cx-r)+b*cq+c)>=0)minx=cx-r; > if((a*x2+b*q2+c)*(a*(cx+r)+b*cq+c)>=0)maxx=cx+r; > if((a*x2+b*q2+c)*(a*cx+b*(cq-r)+c)>=0)minq=cq-r; > if((a*x2+b*q2+c)*(a*cx+b*(cq+r)+c)>=0)maxq=cq+r; > minx=roundup(minx); > maxx=rounddown(maxx); > minq=roundup(minq); > maxq=rounddown(maxq); > if(minx<-1000)minx=-1000;if(minq<-1000)minq=-1000; > if(maxx>1000)maxx=1000;if(maxq>1000)maxq=1000; > printf("%0.0lf",fabs((maxx-minx)*(maxq-minq))); > return 0; > } ?? you still wa !! Yes You are still WA!!!!!!?!!!!!!! Edited by author 16.10.2006 22:21 When I solved this problem then understood that I don't know how humanly round down float to int in C++, because int(double) round down positive numbers but round up negative. Now I use int(x+1000000000)-1000000000, but it is bad. Any ideas ... why don't you use floor() function? Good idea. It is possible to use int(floor()). Nowhere could find proper function. Thnks. Thank you Kovalioff! You are so generous! But why did you stop submiting tasks... If you whant I'll send you a source of task 1370=) Ofcourse it's a joke. Edited by author 21.07.2005 15:59 I've computed that circle center is at 482.05 611.47, radius is 6.08 and the bounding rectangle is x1=476.00 y1=611.47 x2=487.00 y2=617.55. So after rounding the answer should be 11*7 = 77, not 66. Why is it 66? Oh, never mind I just didn't know what an arc was :-) VAR X0, X1, X2 : Extended; Y0, Y1, Y2 : Extended; A, B, C : Extended; A0, B0, C0 : Extended; A1, B1, C1 : Extended; CX, CY, R : Extended; MinX, MaxX, MinY, MaxY : Extended; FUNCTION MyRoundA(A : Extended) : Extended; BEGIN IF Trunc(A) = A THEN MyRoundA := A ELSE MyRoundA := Trunc(A)+1 END; FUNCTION MyRoundB(A : Extended) : Extended; BEGIN IF Trunc(A) = A THEN MyRoundB := A ELSE MyRoundB := Trunc(A)-1 END; BEGIN ReadLn(X0, Y0); ReadLn(X1, Y1); ReadLn(X2, Y2); MinX := X0; IF MinX > X1 THEN MinX := X1; MaxX := X0; IF MaxX < X1 THEN MaxX := X1; MinY := Y0; IF MinY > Y1 THEN MinY := Y1; MaxY := Y0; IF MaxY < Y1 THEN MaxY := Y1; CX := (X0+X1)/2; CY := (Y0+Y1)/2; A := (Y1-Y0); B := (X0-X1); C := X1*Y0-X0*Y1; IF (A <> 0) THEN BEGIN A0 := B/A; B0 := -1; C0 := CY-A0*CX; END ELSE BEGIN A0 := 1; B0 := 0; C0 := -CX; END; CX := (X0+X2)/2; CY := (Y0+Y2)/2; A := (Y2-Y0); B := (X0-X2); C := X2*Y0-X0*Y2; IF (A <> 0) THEN BEGIN A1 := B/A; B1 := -1; C1 := CY-A1*CX; END ELSE BEGIN A1 := 1; B1 := 0; C1 := -CX; END; {center} CX := (B0*C1-B1*C0)/(A0*B1-A1*B0); CY := (A1*C0-A0*C1)/(A0*B1-A1*B0); {radius} R := Sqrt(Sqr(X0-CX)+Sqr(Y0-CY)); {Line (X0,Y0) to (X1,Y1)} A := (Y1-Y0); B := (X0-X1); C := X1*Y0-X0*Y1; IF (A*X2+B*Y2+C)*(A*(CX-R)+B*CY+C) >= 0 THEN MinX := CX-R; IF (A*X2+B*Y2+C)*(A*(CX+R)+B*CY+C) >= 0 THEN MaxX := CX+R; IF (A*X2+B*Y2+C)*(A*CX+B*(CY-R)+C) >= 0 THEN MinY := CY-R; IF (A*X2+B*Y2+C)*(A*CX+B*(CY+R)+C) >= 0 THEN MaxY := CY+R; MinX := MyRoundB(MinX); MaxX := MyRoundA(MaxX); MinY := MyRoundB(MinY); MaxY := MyRoundA(MaxY); IF MinX < -1000 THEN MinX := -1000; IF MinY < -1000 THEN MinY := -1000; IF MaxX > 1000 THEN MaxX := 1000; IF MaxY > 1000 THEN MaxY := 1000; Write((MaxX-MinX)*(MaxY-MinY):0:0); END. {$N+} {$E-} VAR X0, X1, X2 : Extended; Y0, Y1, Y2 : Extended; A, B, C : Extended; A0, B0, C0 : Extended; A1, B1, C1 : Extended; CX, CY, R : Extended; MinX, MaxX, MinY, MaxY : Extended; FUNCTION MyRoundUp(A : Extended) : Extended; BEGIN IF Trunc(A) = A THEN MyRoundUp := Trunc(A) ELSE IF A > 0 THEN MyRoundUp := Trunc(A+1) ELSE MyRoundUp := Trunc(A) END; FUNCTION MyRoundDown(A : Extended) : Extended; BEGIN IF Trunc(A) = A THEN MyRoundDown := Trunc(A) ELSE IF A < 0 THEN MyRoundDown := Trunc(A-1) ELSE MyRoundDown := Trunc(A); END; BEGIN ReadLn(X0, Y0); ReadLn(X1, Y1); ReadLn(X2, Y2); MinX := X0; IF MinX > X1 THEN MinX := X1; MaxX := X0; IF MaxX < X1 THEN MaxX := X1; MinY := Y0; IF MinY > Y1 THEN MinY := Y1; MaxY := Y0; IF MaxY < Y1 THEN MaxY := Y1; CX := (X0+X1)/2; CY := (Y0+Y1)/2; {Line (X0,Y0) to (X1,Y1)} A := (Y1-Y0); B := (X0-X1); C := X1*Y0-X0*Y1; IF (Y1 <> Y0) THEN BEGIN A0 := B/A; B0 := -1; C0 := CY-A0*CX; END ELSE BEGIN A0 := 1; B0 := 0; C0 := -CX; END; CX := (X0+X2)/2; CY := (Y0+Y2)/2; {Line (X0,Y0) to (X2,Y2)} A := (Y2-Y0); B := (X0-X2); C := X2*Y0-X0*Y2; IF (Y2 <> Y0) THEN BEGIN A1 := B/A; B1 := -1; C1 := CY-A1*CX; END ELSE BEGIN A1 := 1; B1 := 0; C1 := -CX; END; {center} CX := (B0*C1-B1*C0)/(A0*B1-A1*B0); CY := (A1*C0-A0*C1)/(A0*B1-A1*B0); {radius} R := Sqrt(Sqr(X0-CX)+Sqr(Y0-CY)); {Line (X0,Y0) to (X1,Y1)} A := (Y1-Y0); B := (X0-X1); C := X1*Y0-X0*Y1; IF (A*X2+B*Y2+C)*(A*(CX-R)+B*CY+C) > 0 THEN MinX := CX-R; IF (A*X2+B*Y2+C)*(A*(CX+R)+B*CY+C) > 0 THEN MaxX := CX+R; IF (A*X2+B*Y2+C)*(A*CX+B*(CY-R)+C) > 0 THEN MinY := CY-R; IF (A*X2+B*Y2+C)*(A*CX+B*(CY+R)+C) > 0 THEN MaxY := CY+R; MaxX := MyRoundUp(MaxX); MaxY := MyRoundUp(MaxY); MinX := MyRoundDown(MinX); MinY := MyRoundDown(MinY); Write((MaxX-MinX)*(MaxY-MinY):0:0); END. > All tricks are in accurate math, not in programming |
|