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 1103. Pencils and Circles

Show all messages Hide all messages

Help!Why this programme got WA? JLYZOI 4 Jun 2004 09:42
This is my programme which I think it's OK,but got WA in Test 7.
I'm glad to thank you if everyone can give some testdatas.

program ural1103;

{$APPTYPE CONSOLE}

const
        maxn=5000;

type
        point=record
                x,y     :extended;
        end;

var
        po      :array[1..maxn]of point;
        n       :integer;

procedure swap(a,b:integer);
var
        t       :point;
begin
t:=po[a];po[a]:=po[b];po[b]:=t;
end;

function min(a,b:integer):boolean;
begin
min:=(po[b].y-po[a].y>1e-10)or
        ((abs(po[b].y-po[a].y)<1e-10)and(po[b].x-po[a].x>1e-10));
end;

function dis(i,j:point):extended;
begin
dis:=sqrt((i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y));
end;

function cos_(a:point):extended;
begin
cos_:=(dis(a,po[1])*dis(a,po[1])+dis(a,po[2])*dis(a,po[2])
        -dis(po[1],po[2])*dis(po[1],po[2]))/(dis(a,po[1])*dis(a,po[2]));
end;

procedure qsort(p,q:integer);
var
        i,j     :integer;
        x       :point;
begin
if p>=q then exit;
i:=p-1;
j:=q+1;
x:=po[(i+j)div 2];
while(i<j)do
begin
        repeat inc(i);until (cos_(x)-cos_(po[i])>-1e-10);
        repeat dec(j);until (cos_(po[j])-cos_(x)>-1e-10);
        if i<j then swap(i,j);
end;
qsort(p,j);
qsort(j+1,q);
end;

function max(a,b:integer):boolean;
begin
max:=((po[a].x-po[1].x)*(po[b].y-po[1].y)
        -(po[b].x-po[1].x)*(po[a].y-po[1].y))>1e-10;
end;

procedure init;
var
        i       :integer;
begin
read(n);
for i:=1 to n do
        read(po[i].x,po[i].y);
for i:=2 to n do
        if min(i,1) then swap(1,i);
for i:=3 to n do
        if max(i,2) then swap(2,i);
qsort(3,n);
writeln(po[1].x:0:0,' ',po[1].y:0:0);
writeln(po[2].x:0:0,' ',po[2].y:0:0);
writeln(po[(n+3)div 2].x:0:0,' ',po[(n+3)div 2].y:0:0);
end;

begin
  { TODO -oUser -cConsole Main : Insert code here }
  init;
  readln;
//  readln;
end.
I think it is right. liuchang 4 Jun 2004 17:54


Edited by author 04.06.2004 17:55