Show all threads Hide all threads Show all messages Hide all messages |
Wa3 + some advices | Gleb | 1159. Fence | 31 Jul 2018 20:29 | 1 |
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) |
Max tests | Chitanda Eru | 1159. Fence | 17 Mar 2017 15:37 | 1 |
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. |
Funny. | Mukhametianov Den [USU] | 1159. Fence | 17 Mar 2017 15:32 | 3 |
Funny. Mukhametianov Den [USU] 28 Aug 2010 19:10 infin = 100000000 - wa14. infin = 1000000 - ac. Re: Funny. Sergey Lazarev (MSU Tashkent) 4 Jan 2011 23:45 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. |
A useful test | Pong Eksombatchai | 1159. Fence | 28 Aug 2011 05:36 | 1 |
Try 3 3 4 5 The answer should be 6.00 |
upper bound for binary search? why n*(sum of lengths) work? | muhammad | 1159. Fence | 10 Apr 2011 13:53 | 1 |
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. |
Test 1 | Giorgi Shavgulidze [Tbilisi SU] | 1159. Fence | 27 Mar 2011 03:33 | 1 |
Test 1 Giorgi Shavgulidze [Tbilisi SU] 27 Mar 2011 03:33 Isn't answer 40 on T1? trapeze with bases 10 and 4. Edited by author 27.03.2011 03:35 |
My God! How to solve it???????????????????/ | Test4 | 1159. Fence | 21 May 2010 18:56 | 3 |
Hi, if you have some troubles with this problem, I can help you :) Contact me, darkhan.imangaliev@gmail.com< |
What is the answer for test(4 blocks):"4 3 5 20 24"? Is it "76.13" or not? | Nazarov Denis (nsc2001@rambler.ru) | 1159. Fence | 7 May 2009 14:05 | 2 |
|
Ha Ha Ha ~~ I have got the data of this problem ! | Curapica | 1159. Fence | 4 Oct 2005 07:15 | 4 |
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. |
heh, you'll have got a lot of troubles with accuracy | Krayev Alexey(PSU-Again) | 1159. Fence | 4 Aug 2005 14:20 | 1 |
|
How to prove that all the vertices of the max-area polygon share the same circle? | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1159. Fence | 23 Oct 2004 04:56 | 1 |
|
who can help me???i've got WA for mant times | coma | 1159. Fence | 12 Jun 2003 13:45 | 1 |
#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; } |
Can someone help me with this problem? :) (-) | Miguel Angel | 1159. Fence | 12 May 2003 13:56 | 3 |
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. |
Why cannot we use asin, atan, or acos?? [just asinl .. ] (-) | Miguel Angel | 1159. Fence | 2 Dec 2002 03:01 | 3 |
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. |
Why I get WA? Pelase, help me!!!!!!! (+) | Nazarov Denis (nsc2001@rambler.ru) | 1159. Fence | 1 Feb 2002 19:21 | 1 |
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. |
Thanks for Rybak Michael's help.He is kind hearted. | Huang Yizheng | 1159. Fence | 21 Jan 2002 05:21 | 1 |
|
The blocks are used to be erected or put horizontally?The height of the block is useful or useless? | Huang Yizheng | 1159. Fence | 21 Dec 2001 13:31 | 1 |
|
Can anybody explain this problem to me(or email to:"hyz12345678@163.com"),how can the board be cut and enclosure to a fence? | Huang Yizheng | 1159. Fence | 21 Dec 2001 13:26 | 1 |
|
What does this problem mean?I'm confused. | Huang Yizheng | 1159. Fence | 21 Dec 2001 13:25 | 3 |
|
How to do it?help! | blue dog | 1159. Fence | 21 Dec 2001 13:19 | 1 |
|