. Edited by author 23.08.2016 13:56 My AC solution answers YES 1000.000499854463800 0.000000000000000 999.999500145786100 0.999999500145786 to test 0 0 1000 1 2000 0 Another AC program answers YES 1000.000500262685700 0.000000000000000 999.999499737564410 0.999999499737564 Absolute difference of coordinates in answers ~ 10^6, not 10^-9 as required by statement. I think current checker does not check accuracy of coordinates, but rather compare squares and perimeters of figures original triangle split to. Admins, please update limitations of the problem. Either accuracy of coordinates 10^-6 or change it to accuracy of squares and perimeters of resulting figures. And it is important what accuracy required - absolute or relative. Edited by author 27.05.2009 19:32 The answers provided here are correct. And so is the checker. What is algorithm? What formulas, theorems, equations and hints must I use? Is here some adia? =) Suppose that answer is XY, where point X lies on CA and Y lies on CB. Then let CX = x, CY = y. Now you have two equations: x + y = P/2, x * y = CA * CB / 2 (P is perimeter). The rest of solution is straightforward. Thank you very much! Very good adia! P.S.: How get x * y = CA * CB / 2 ? Just simple: 2 * SQUARE_CXY == SQUARE_ABX 2 * 0.5 * x * y * sinXCY == 0.5 * CA * CB * sinXCY x * y == 0.5 * CA * CB x * y = CA * CB / 2 I think about it several minute. =) Why? I pass the given tests correctly. BTW, the problem can have several answers, :S I had WA#1, then WA#22. Can somebody help me? I think there are problems with precision. Wow, I also have WA#22 now. BTW, my WA#1 was because I didn't #include <math.h> LOL AC now))) Using epsilon in some more places helped me a lot! Yes!Agree.Impossible get Ac without eps. Please, who can explain me why epsilon is needed in problems which contain real numbers, and where should I use it in this problem? I got WA#22, and can't understand my mistake. There are many trick with epsilon. For example. Let eps=1e-10 and some geometrical value d calculated as -1.e-11. We reject this calculation because d must be >=0 and make mistake lossing d=0. With eps we do it as if (fabs(d)<=eps) d=0 thus accepting negative -1e-11. When I used eps=1e-13, I got WA #22, and when I chaged it to 1e-10, I got AC. Here are fragments, where I use eps: ... double d=p*p-2*a*b; if(fabs(d)<eps) ... (d is discriminant of square equation) ... if(t1>a+eps || t2>b+eps) return false; ... (check that t1<=a and t2<=b). I can't understand why I had this situation. Maybe the numbers are big, so adding 1e-13 is equal to adding 0. eps = 1e-10 thanks! Edited by author 30.07.2011 02:06 Edited by author 30.07.2011 02:06 According formule S=sqrt(p*(p-a)*(p-b)*(p-c)) => the problem has 3 different answers. No! Sample #2 has only one answer. program Project1; {$APPTYPE CONSOLE} uses SysUtils; type point=record x,y:extended; end; function dist(a,b:point):extended; begin dist:=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); end; procedure readp(var a:point); begin read(a.x,a.y); end; procedure searchXY(a,b,c:extended; var x,y:extended); var p:extended; begin p:=(a+b+c)/2; if p*p-2*a*b<0 then begin x:=maxlongint; y:=maxlongint; exit; end; x:=(p+sqrt(p*p-2*a*b))/2; y:=(p-sqrt(p*p-2*a*b))/2; end; var A,B,C:point; aa,bb,cc,x,y:extended; flagg:integer; procedure print(a:point; x:extended; b:point; y:extended; c:point); var CA,CB:point; begin CA.x:=a.x-c.x; CA.y:=a.y-c.y; CB.x:=b.x-c.x; CB.y:=b.y-c.y; if (x/dist(a,c)*CA.x=y/dist(b,c)*CB.x)and(x/dist(a,c)*CA.y=y/dist(b,c)*CB.y) then begin flagg:=1; exit; end; writeln(x/dist(a,c)*CA.x+c.x:0:9,' ',x/dist(a,c)*CA.y+c.y:0:9); writeln(y/dist(b,c)*CB.x+c.x:0:9,' ',y/dist(b,c)*CB.y+c.y:0:9); end; begin readp(A); readp(B); readp(C); aa:=dist(B,C); bb:=dist(A,C); cc:=dist(A,B); searchXY(aa,bb,cc,x,y); flagg:=0; if (x<aa)and(y<bb)and(x<>maxlongint) then begin writeln('YES'); print(b,x,a,y,c); if flagg=0 then halt; end; flagg:=0; if (x<bb)and(y<aa)and(x<>maxlongint) then begin writeln('YES'); print(a,x,b,y,c); if flagg=0 then halt; end; searchXY(aa,cc,bb,x,y); flagg:=0; if (x<aa)and(y<cc)and(x<>maxlongint) then begin writeln('YES'); print(c,x,a,y,b); if flagg=0 then halt; end; flagg:=0; if (x<cc)and(y<aa)and(x<>maxlongint) then begin writeln('YES'); print(a,x,c,y,b); if flagg=0 then halt; end; flagg:=0; searchXY(bb,cc,aa,x,y); if (x<bb)and(y<cc)and(x<>maxlongint) then begin writeln('YES'); print(c,x,b,y,a); if flagg=0 then halt; end; flagg:=0; if (x<cc)and(y<bb)and(x<>maxlongint) then begin writeln('YES'); print(b,x,c,y,a); if flagg=0 then halt; end; writeln('NO'); end. I know that it's "bugcode", but.. In this problem, I find the root of the equation 2*x*x - p*x + AB*AC = 0. However, I get WA test 2. I think it's due to 1e-9 accuracy Can anyone show me some hints to solve this problem? Edited by author 31.05.2009 23:21 Edited by author 31.05.2009 23:21 Please give me some help. a test or smth. I passed test 3 when changed Heron formula to vector product. Hi everybody! Please run your AC programs on this test: 0 0 1000 1 2000 0 And post you result with name of compiler you use. Thank you! YES 999.999499737564410 0.999999499737564 1000.000500262685700 0.000000000000000 P.S. Compiler - VS C++. My prog got AC Edited by author 25.10.2008 21:24 Thanks! But it is incorrect answer. Precision is not enough. I think jury must change precision to 1e-3 or add this test and make rejudge... Edited by author 25.10.2008 21:53 Correct - my solution is analytical. Think why this is another correct answer but obvious "1000 0 1000 1". It is analytical but not so exact. Actually some analytical solution can use more square root and so on and give not so exact result... If this test will be added (and some similar) than many AC solution will fail. What means "Not so exact"??? Perimeter of one part - 2000.0004999998749789068277343249 Perimeter of another part - 2000.0004999998750212181721875511 Area of one part - 499.9999999999997186851059078174 Area of another part - 500.0000000000002813148940921826 Don't you see some similarity in them? Up to 10^-12! Thank you. Now I understood that in this case we have 3 solution one of them: 1000 0 1000 1 - the median of triangle and 2 another similar to your result. Sorry for flood Victor Barinov (TNU) Help me please I choose method with median... but i have WA#2 #include <iostream> #include <math.h> using namespace std; int main() { double x1,y1,x2,y2,x3,y3,a,b,c; double X1,X2,Y1,Y2,X,Y,X0,Y0; cout.precision(15); cout.setf(ios::fixed); cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3; a = sqrt((double)pow(x1-x2,2)+pow(y1-y2,2)); b = sqrt((double)pow(x1-x3,2)+pow(y1-y3,2)); c = sqrt((double)pow(x2-x3,2)+pow(y2-y3,2)); // Finding big side of triangle if (a > b && a > c) { X1 = x1; Y1 = y1; X2 = x2; Y2 = y2; X0 = x3; Y0 = y3; } else if (b > a && b > c) { X1 = x1; Y1 = y1; X2 = x3; Y2 = y3; X0 = x2; Y0 = y2; } else if (c > a && c > b) { X1 = x2; Y1 = y2; X2 = x3; Y2 = y3; X0 = x1; Y0 = y1; } X = (X1 + X2) / 2; Y = (Y1 + Y2) / 2; cout<<"YES"<<endl<<X0<<" "<<Y0<<endl; cout<<X<<" "<<Y; return 0; } Why the segment ST can be the middle-line of the triangle. If a is the longest edge and b is not equal with c, the solution can work out a right answer? |
|