ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1348. Goat in the Garden 2

I would really appreciate any test for this problem,WA#19
Posted by MNV 4 Jan 2006 22:39
This is my solution for the problem,which,as you might have already understood,gets WA at the 19-th test.

Dot function returns the dot product of given 2 2-dimension vectors,which according to the formulae dot(a,b)=|a|*|b|*cos(a^b),would be less than zero in the case of a triangle with an angle of more than 90*.(Imagine that).

I would be grateful for any comments or tests.

{$N+}
program Goatish2;
var
  ax,ay,bx,by,cx,cy,ans1,ans2,a,b,c,minx,miny,maxx,maxy:double;
  l:integer;

function dot:double;
begin
  dot:=((cx-minx)*(maxx-minx)+(cy-miny)*(maxy-miny));
end;

begin
  readln(ax,ay,bx,by);
  readln(cx,cy,l);
  a:=(ay-by);b:=(bx-ax);c:=by*ax-bx*ay;
  if (a<>0) or (b<>0) then begin
  ans1:=abs(a*cx+b*cy+c)/sqrt(a*a+b*b);
  if ((cx-ax)*(cx-ax)+(cy-ay)*(cy-ay))<((cx-bx)*(cx-bx)+(cy-by)*(cy-by)) then
  begin
    minx:=ax;miny:=ay;maxx:=bx;maxy:=by;
  end else begin
    minx:=bx;miny:=by;maxx:=ax;maxy:=ay;
  end;
  if dot>0 then ans1:=ans1-l else
  ans1:=sqrt((cx-minx)*(cx-minx)+(cy-miny)*(cy-miny))-l;
  ans2:=sqrt((cx-maxx)*(cx-maxx)+(cy-maxy)*(cy-maxy))-l;
  end else begin
    ans1:=sqrt((cx-ax)*(cx-ax)+(cx-ay)*(cx-ay))-l;ans2:=ans1;
  end;
  if ans1<0 then ans1:=0;if ans2<0 then ans2:=0;
  writeln(ans1:0:2);writeln(ans2:0:2);
end.

Edited by author 05.01.2006 22:08
Re: I would really appreciate any test for this problem,WA#19
Posted by MNV 4 Jan 2006 23:56
The cases of
-obtuse||acute triangle;
-point lying on AB;
-A&B with similar coordinates
were taken into consideration.

Edited by author 05.01.2006 00:08
Re: I would really appreciate any test for this problem,WA#19
Posted by MNV 5 Jan 2006 22:02
Does ANYONE know any test for this problem,which the programme is particularly unlikely to cope with?
Please,HELP!
Re: I would really appreciate any test for this problem,WA#19
Posted by jedimastex 6 Jan 2006 13:54
This algo is AC:
 find AC, BC, AB
 if ABC>90 or BAC>90 then ans1=min(AB,AC) else
   find 2*S(ABC) (I used abs([AC^,AB^]) )
   ans1=2*S(ABC)/AB
  ans2=max(AC,BC)

This is my s(a,b,c) where a,b,c are points (x,y)

function s(var a,b,c:point):double;
begin
 s:=abs(a.x*(b.y-c.y)-a.y*(b.x-c.x)+(b.x*c.y-c.x*b.y));
end;

Edited by author 06.01.2006 13:57
Re: I would really appreciate any test for this problem,WA#19
Posted by MNV 6 Jan 2006 17:53
OK,I'll try to implement and test it.
Though I still don't know what's wrong with my own code.
Re: I would really appreciate any test for this problem,WA#19
Posted by jedimastex 9 Jan 2006 22:57
Are you ever going to submit this problem?
I can mail my AC-code on request.
Why are you IUnknown now?
Re: I would really appreciate any test for this problem,WA#19
Posted by IUnknown 9 Jan 2006 23:36
Yes,I am going to,but right now I have some other interesting problems to solve,so my preference is to develop an algorithm rather than working on the perfection of implemention.Thanx,I don't need your code.
About my nickname,well,I had some reasons for doing that.
I see:)
Posted by jedimastex 10 Jan 2006 18:23
quote: about my nickname,well,I had some reasons for doing that:)
Your code has a fatal error due to machine limitations.
You should rewrite it using another algo that would not involve such complex calculations.