Wa3 - answer is 0.00. there you should check the longest block ;) I counted radius with precision 1e-10, upper bound is 1e6. P.s. dont forget cases there center of circle is outside(like sample) For the max test (a hundred 100's) the answer is 7955128.99. For ninety nine 1m sides and one 98m side it's 397.86. Use this to check your precision. infin = 100000000 - wa14. infin = 1000000 - ac. Thank you! But it's very strange. I found the radius using bin search. The right border for search was the sum of all lengths - it must be greater than radius. And I've got WA 14. After changing right border to 10^6 I've got AC. If you try to check a very big radius, the parameter of arcsin gets very low. I assume the function just returns its parameter if it's very close to 0 but your eps needs to be very low as well. Also, the raduis of a polygon's circumscribed circle can be infinitely large no matter what's the upper boundary for its sides is. In this problem, there is a lower boundary too, so you can actually limit your binary search with something. Try 3 3 4 5 The answer should be 6.00 i used 1e8 first and got wa14 latter used n*(sum of edge lengths) and got ac. i found that for test 14 the curve goes up and at r=200.75 touches x axis then goes up until x=around 450 then down again with asymptote as x axis. so i tried to use tenary search to find upper bound but it does not always work. why n*sum of lengths work? is it weak tests or can somebody prove optimal upper bound? please, help me understand. thanks in advance. Isn't answer 40 on T1? trapeze with bases 10 and 4. Edited by author 27.03.2011 03:35 Hi, if you have some troubles with this problem, I can help you :) Contact me, darkhan.imangaliev@gmail.com< I have got the data of this problem ! Do you want it? Contact Me, and I will give it to you, my dear! My Email : MartinKanglh@hotmail.com Do Remember Me! My name is Martin.Kang Something about this problem : the precision of this problem is very abnormality, you must make it as 1e-8, and make the maximal answer as 1e8, then you can pass the data and get accept. Thank You very MUCH!!! I've got AC using Your hint about maximal possible circle radius! You (reader, who hasn't AC this beautiful problem) should use the MaxRadius which equal at least 1,000,000. Thank you for your advise. I got AC too. btw : I used a precision of 1.0e-13 and I made the maximal radius 1.0e10(1.0e6 will get WA), so that I got AC. Hope this helpful to others. Anyone want data? Just Google it. But I don't think it's very nice unless you're agonized of this problem. And I got AC without getting any test cases except the ones I made. #include <stdio.h> #include <math.h> #define PI 3.1415926535 double a[101]; int n; void init() { int i,k; double t; scanf("%d",&n); k=1; for (i=1;i<=n;i++) { scanf("%lf",&a[i]); if (a[i]>a[k]) k=i; } t=a[1]; a[1]=a[k]; a[k]=t; } double hl(double r,int k) { double p; double s; p=(a[k]+r+r)/2; s=p*(p-a[k])*(p-r)*(p-r); return (sqrt(s)); } double find_s(int k,double r) { int i; double s; if (k==0) s=-hl(r,1); else s=hl(r,1); for (i=2;i<=n;i++) s=s+hl(r,i); return (s); } double judge(int k,double r) { double deg; int i; double b,c; if (k==0) deg=2*PI-acos(1-(a[1]*a[1])/(2*r*r)); else deg=acos(1-(a[1]*a[1])/(2*r*r)); for (i=2;i<=n;i++) deg=deg+acos(1-(a[i]*a[i])/(2*r*r)); return (deg); } void solve() { int i,k; double high,low,l; double mid; low=a[1]/2;high=1000000; k=0; if (judge(1,low)>2*PI) k=1; else k=0; while (high-low>0.00001) { mid=(high+low)/2; l=judge(k,mid); if (k==1) { if (l>PI*2) low=mid; else high=mid; } if (k==0) { if (l>PI*2) high=mid; else low=mid; } } printf("%.2lf\n",find_s(k,mid)); } main() { int i; double sum; init(); sum=0; for (i=2;i<=n;i++) sum=sum+a[i]; if (sum<=a[1]) printf("0.00\n"); else solve(); return 0; } The resulting polygon must fir-in the circle. You only need to determine circle radius and to check for possibility of the polygon existance (extended triangle inequality). To determine radiuse something like binary search is used. System of equations is very simple and is solved that way. Tip: be careful with the test when the center of circle is outside of polygon. P.S. Sorry for bad mathematical english... > It's clear that the area is a convex polygon,and all its vertexs share a comman circle. Actually Pascal&Delphi have only ArcTan(x). ArcSin(x) is calculted as ArcSin(x) := ArcTan(x/sqrt(1-sqr(x))); ArcCos(x) := ArcTan(sqrt(1-sqr(x))/x); That is. > Actually Pascal&Delphi have only ArcTan(x). > ArcSin(x) is calculted as > ArcSin(x) := ArcTan(x/sqrt(1-sqr(x))); > ArcCos(x) := ArcTan(sqrt(1-sqr(x))/x); > That is. My program: Program t1159;{$N+} Const MaxN = 100; Change = 180/Pi; OkW = 360.0; Eps = 1E-15; Eps2 = 1E-3; Var Block : array[1..MaxN]of integer; N,i,sum,max : integer; mx,t : integer; left,rigth : extended; middle : extended; curW : extended; ok : boolean; Function GetLW(R : extended;L : integer) : extended; Var cosw,w,tgw : extended; begin cosw:=(2*R*R-L*L)/(2*R*R); if cosw=0 then w:=90 else begin tgw:=sqrt(1-cosw*cosw)/cosw; w:=ArcTan(tgw)*Change; if w<0 then w:=180+w; end; GetLW:=w; end; Function GetW(R : extended) : extended; Var w : extended; j : integer; begin w:=0; for j:=1 to N do w:=w+GetLW(R,Block[j]); GetW:=w; end; Function GetS(R : extended) : extended; Var Ans,p,S : extended; i : integer; begin Ans:=0; for i:=1 to N do begin p:=(2*R+Block[i])/2; S:=sqrt(abs(p*(p-R)*(p-R)*(p-Block[i]))); Ans:=Ans+S; end; GetS:=Ans; end; Procedure WriteAns(R : extended); begin Writeln(GetS(R):0:2); Halt(0); end; Procedure WriteAns2(R : extended); Var S,p : extended; begin p:=(2*R+Block[N+1])/2; S:=sqrt(p*(p-R)*(p-R)*(p-Block[N+1])); Writeln(GetS(R)-S:0:2); {Halt(0);} end; begin Read(N); sum:=0; max:=0; for i:=1 to N do begin Read(Block[i]); sum:=sum+Block[i]; if Block[i]>max then begin max:=Block[i]; mx:=i; end; end; if mx<>N then begin t:=Block[mx]; Block[mx]:=Block[N]; Block[N]:=t; end; if max>=sum-max then begin writeln('0.00'); halt(0); end; if max mod 2=0 then max:=max div 2 else max:=1+(max div 2); left:=max; rigth:=sum; While True do begin middle:=(left+rigth)/2; curW:=GetW(middle); if curW<OkW then rigth:=middle else left:=middle; if rigth-left<Eps then break; end; if abs(curW-OkW)<Eps2 then WriteAns(middle); N:=N-1; left:=max; rigth:=1E10; While True do begin middle:=(left+rigth)/2; curW:=GetW(middle); if curW>GetLW(middle,Block[N+1]) then rigth:=middle else left:=middle; if rigth-left<Eps then break; end; writeans2(middle); end. |
|