.

Edited by author 23.08.2016 13:56

What is algorithm? What formulas, theorems, equations and hints must I use?

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

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

Please give me some help. a test or smth.

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!

Why? I pass the given tests correctly.

BTW, the problem can have several answers, :S