Why I always WA on text 2?

New tests were added. 123 authors lost AC after rejudge.

 var
  a:array[0..1000,1..3] of real;

  x,y,x0,y0:real;
  n,i,j,k:integer;
begin
  readln(x0,y0);
  readln(n);
  fillchar(a,sizeof(A),0);
  for i:=1 to n do begin
    readln(x,y,a[i,3]);
    x:=x-x0;y:=y-y0;
    a[i,1]:=x;a[i,2]:=y;
  end;
  for i:=1 to n-1 do for j:=i+1 to n do if a[i,1]*a[j,2]-a[i,2]*a[j,1]
>0 then begin
    a[0]:=a[i];a[i]:=a[j];a[j]:=a[0];
  end;
  writeln(0);
  for i:=1 to n do begin
    writeln(a[i,3]:0:0);
  end;
  writeln(0);
end.

 On the 1st line of input, there will be 2 real numbers: X and Y, separated by a blank, representing the coordinates of Wally's house. On the 2nd line, there will be an integer number: N (2 <= N <= 1000),

my program

var
 x,y,n:longint;
begin
readln(x,y);
readln(n);
while n=0 do begin end;
end.

Why i got TLE test1?????
N=2...1000
test 1 correct????

First i build convex hull, then for the rest of points i choose the nearest point to convex hull and include it in  hull. But i get wa#2 all the time. So I suppose that either tests incorrect (for example 3 points share the same line) or checker is incorrect.
Maybe of course i made mistake but i spent a day finding it and nothing. People, help me please!!!!!!



#include <list>
#include <math.h>
using namespace std;
#define sqr(x) ((x)*(x))
typedef list<int> ilist;
typedef ilist::iterator ilit;
#define eps 1e-8
struct tp{
    double x, y;
    int id;
};
//int cnt;
tp pt[1003];
int npt, n, cnt1;
int comp[1003];
double tdist[1003];
ilit to[1003];
ilist reshull;
int fres;

double getlen(tp &p1, tp &p2){//checked
    return sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y));
}

int above(tp &p1, tp &p2, tp &what){//checked
    double temp;
    temp=((p2.x-p1.x)*(what.y-p1.y)-(p2.y-p1.y)*(what.x-p1.x));
    if (temp>eps) return 1;
    else if (temp<-eps) return -1;
    else return 0;
}
double getdist(tp &p1, tp &p2, tp &what){//checked
    return fabs((p2.x-p1.x)*(what.y-p1.y)-(p2.y-p1.y)*(what.x-p1.x))/getlen(p1, p2);
}
void quickhull(tp &start, tp &fin, ilit forins){//checked
    int oldcnt=cnt1;
    int i, maxi;
    double maxdist=-1, dist;
    bool is=false;
    ilit newp;
    for (i=1; i<=n+1; i++)
        if (comp[i]==oldcnt){
            is=true;
            dist=getdist(start, fin, pt[i]);
            if (dist>maxdist){
                maxdist=dist;
                maxi=i;
            }
        }
    if (!is) return ;
    newp=forins; newp++;
    newp=reshull.insert(newp, maxi);
    cnt1++;
    for (i=1; i<=n+1; i++)
        if (comp[i]==oldcnt && i!=maxi){
            fres=above(start, pt[maxi], pt[i]);
            if (fres==1) comp[i]=cnt1;
            else if (fres==0) while (true) i=i;
        }
    quickhull(start, pt[maxi], forins);
    cnt1++;
    for (i=1; i<=n+1; i++)
        if (comp[i]==oldcnt && i!=maxi){
            fres=above(pt[maxi], fin, pt[i]);
            if (fres==1) comp[i]=cnt1;
            else if (fres==0) while (true) i=i;
        }
    quickhull(pt[maxi], fin, newp);

}
double getdist1(tp &p1, tp &p2, tp &what){//checked
    double w1, w2;
    w1=(p2.x-p1.x)*(what.x-p1.x)+(p2.y-p1.y)*(what.y-p1.y);
    w2=(what.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(what.y-p2.y);
    if (w1>eps && w2>eps) return getdist(p1, p2, what);
    else if (w1<eps) return getlen(p1, what);
    else return getlen(p2, what);
}
int main(){//checked
#ifndef ONLINE_JUDGE
    freopen("i.txt","r", stdin);
    freopen("o.txt", "w", stdout);
#endif
    scanf("%lf %lf", &pt[1].x, &pt[1].y);
    pt[1].id=0;
//    npt=1;
    scanf("%d", &n);
    int i;
//    if (n>20) while (true) i=i;

    for (i=2; i<=n+1; i++){
        scanf("%lf%lf%d", &pt[i].x, &pt[i].y, &pt[i].id);
    }
    int maxx, minx;
    maxx=minx=1;
    for (i=2; i<=n+1; i++){
        if (pt[minx].x>pt[i].x) minx=i;
        if (pt[maxx].x<pt[i].x) maxx=i;
    }
    reshull.push_front(minx);
    reshull.push_back(maxx);
    //p2=reshull.begin(); p2++;
    cnt1++;
    for (i=1; i<=n+1; i++)
        if (i!=minx && i!=maxx){
            fres=above(pt[minx], pt[maxx], pt[i]);
            if (fres==1)
                comp[i]=cnt1;
            else if (fres==0) while (true) i=i;
        }

    ilit p1, p2, p3;
    p2=p1=reshull.begin();
    p2++;
    quickhull(pt[minx], pt[maxx], p1);
    cnt1++;
    for (i=1; i<=n+1; i++)
        if (i!=minx && i!=maxx){
            if (above(pt[minx], pt[maxx], pt[i])==-1)
                comp[i]=cnt1;
        }
    quickhull(pt[maxx], pt[minx], p2);
    int inhull=0;
    for (p1=reshull.begin(); p1!=reshull.end(); p1++){
        i=pt[*p1].id;
        tdist[*p1]=-1;
        inhull++;
    }
    double tempdist, tempdist1;
    reshull.push_back(minx);
    for (i=1; i<=n+1; i++)
        if (tdist[i]!=-1){
            tdist[i]=100000000l;
            for (p2=p1=reshull.begin(), p1++; p1!=reshull.end(); p1++, p2++){
                tempdist=getdist1(pt[*p2], pt[*p1], pt[i]);
                if (tdist[i]>tempdist){
                    tdist[i]=tempdist;
                    to[i]=p2;
                }
            }

        }
    int j;
    int mini;
    for (j=1; j<=n+1-inhull; j++){
        mini=-1;
        for (i=1; i<=n+1; i++)
            if (tdist[i]!=-1 && (mini==-1 || tdist[i]<tdist[mini])) mini=i;
        tdist[mini]=-1;
        p3=p1=to[mini];
        i=*p3;
        i=*(p3++);
        p2=reshull.insert(p3, mini);
        for (i=1; i<=n+1; i++)
            if (tdist[i]!=-1){
                tempdist=getdist1(pt[*p1], pt[*p2], pt[i]);
                tempdist1=getdist1(pt[*p2], pt[*p3], pt[i]);
                if (tdist[i]>tempdist-eps){
                    tdist[i]=tempdist;
                    to[i]=p1;
                }
                if (tdist[i]>tempdist1-eps){
                    tdist[i]=tempdist1;
                    to[i]=p2;
                }

            }
    }
    if (pt[*(p1=reshull.begin())].id==0){
        for (; p1!=reshull.end(); p1++)
            printf("%d\n", pt[*p1].id);
        return 0;

    }

    for (p1=reshull.begin(); pt[i=(*p1)].id!=0; p1++)
        i=i;
    printf("0\n");
    for (p1++; p1!=reshull.end(); p1++)
        printf("%d\n", pt[i=*p1].id);
    p1=reshull.begin(); p1++;
    for (; pt[*p1].id!=0; p1++)
        printf("%d\n", pt[i=*p1].id);
    printf("0\n");

    return 0;
}

Edited by author 11.08.2005 19:32

var
i,j,k,n,m,s:longint;
xx:real;
x,y:array[0..1000] of real;
a:Array[0..1000] of integer;
an:array[0..1000] of real;
d:array[0..1000] of integer;
begin
  readln(x[0],y[0]);
  readln(n);
  for i:=1 to n do
  readln(x[i],y[i],d[i]);
  for i:=1 to n do
  begin
    x[i]:=x[i]-x[0];
    y[i]:=y[i]-y[0];
  end;
  for i:=1 to n do
    for j:=i+1 to n do
    if ((x[i]=x[j]) and (y[i]=y[j])) or ((x[i]=0) and (y[i]=0))then
    begin
      writeln(-1);
      halt;
    end;
  writeln(0);
  fillchar(a,sizeof(a),0);
  fillchar(an,sizeof(an),0);
  s:=0;
  for i:=1 to n do
  if (x[i]=0) and (y[i]>0) then writeln(i);

  for i:=1 to n do
  if (x[i]>0) and (y[i]>=0) then
  begin
    inc(s);
    a[s]:=i;
    an[s]:=arctan(y[i]/x[i]);
  end;
  for i:=1 to s-1 do
    for j:=1 to s-i do
    if an[j]<an[j+1] then
    begin
      k:=a[j];
      a[j]:=a[j+1];
      a[j+1]:=k;
      xx:=an[j];
      an[j]:=an[j+1];
      an[j+1]:=xx;
    end;
  for i:=1 to s do
  writeln(d[a[i]]);

  fillchar(a,sizeof(a),0);
  fillchar(an,sizeof(an),0);
  s:=0;
  for i:=1 to n do
  if (x[i]>0) and (y[i]<0) then
  begin
    inc(s);
    a[s]:=i;
    an[s]:=arctan(-1*y[i]/x[i]);
  end;
  for i:=1 to s-1 do
    for j:=1 to s-i do
    if an[j]>an[j+1] then
    begin
      k:=a[j];
      a[j]:=a[j+1];
      a[j+1]:=k;
      xx:=an[j];
      an[j]:=an[j+1];
      an[j+1]:=xx;
    end;
  for i:=1 to s do
  writeln(d[a[i]]);

  for i:=1 to n do
  if (x[i]=0) and (y[i]<0) then writeln(i);

  fillchar(a,sizeof(a),0);
  fillchar(an,sizeof(an),0);
  s:=0;
  for i:=1 to n do
  if (x[i]<0) and (y[i]<=0) then
  begin
    inc(s);
    a[s]:=i;
    an[s]:=arctan(y[i]/x[i]);
  end;
  for i:=1 to s-1 do
    for j:=1 to s-i do
    if an[j]<an[j+1] then
    begin
      k:=a[j];
      a[j]:=a[j+1];
      a[j+1]:=k;
      xx:=an[j];
      an[j]:=an[j+1];
      an[j+1]:=xx;
    end;
  for i:=1 to s do
  writeln(d[a[i]]);

  fillchar(a,sizeof(a),0);
  fillchar(an,sizeof(an),0);
  s:=0;
  for i:=1 to n do
  if (x[i]<0) and (y[i]>0) then
  begin
    inc(s);
    a[s]:=i;
    an[s]:=arctan(-1*y[i]/x[i]);
  end;
  for i:=1 to s-1 do
    for j:=1 to s-i do
    if an[j]>an[j+1] then
    begin
      k:=a[j];
      a[j]:=a[j+1];
      a[j+1]:=k;
      xx:=an[j];
      an[j]:=an[j+1];
      an[j+1]:=xx;
    end;
  for i:=1 to s do
  writeln(d[a[i]]);
  writeln(0);
end.

First i calculate the degree between wally house and every friend by
procedure ATG and then sort friends by their degree...

Type
  Point               =record
    x,y,d             :real;
    ID                :Integer;
  end;
Var
  a                   :array[0..1000] of point;
  n,i                 :integer;

function partition(first,last:integer):integer;
Var
  t                   :point;
  i,j                 :integer;
  x                   :real;
begin
  i:=first-1;
  j:=last+1;
  x:=a[first].d;
  while true do
  begin
    repeat inc(i);
    until a[i].d<=x;
    repeat dec(j);
    until a[j].d>=x;
    if i<j then begin
      t:=a[i]; a[i]:=a[j]; a[j]:=t; end
    else begin
      partition:=j; exit; end;
  end;
end;

Procedure qsort(first,last:integer);
Var
  w                   :integer;
begin
  if first<last then
  begin
    w:=partition(first,last);
    qsort(first,w);
    qsort(w+1,last);
  end;
end;

Function ATG(x:integer):real;
Var
  dx,dy,k             :real;
begin
  dx:=a[x].x-a[0].x;
  dy:=a[x].y-a[0].y;
  if dx=0 then
    k:=90
  else
    k:=arctan(dy/dx)/pi*180;
  if (k<0) or ((k=0) and (dx<0)) then k:=k+180;
  if dy<0 then k:=k+180;
  atg:=k;
end;

begin
  readln(a[0].x,a[0].y);
  readln(n);
  for i:=1 to n do
  begin
    readln(a[i].x,a[i].y,a[i].ID);
    a[i].d:=ATG(i);
  end;
  qsort(1,n);
  writeln(0);
  for i:=1 to n do
    writeln(a[i].Id);
  writeln(0);
end.

Hi
I calculate every friend`s degree to wally house and then sort them
and with a little bit change write them...
but i know there is another way to swap endpoint of line if two line
cut eachother such as
*    *
 *  *
  **
  **
 *  *
*    *
Gets
*    *
*    *
*    *
*    *
*    *
*    *
anyonw want to change his solutin with mine?
Aidin_n7@hotmail.com

const
   limit        =1000;

type
   Tnode        =record
                     id         :integer;
                     dig        :extended;
                 end;

var
   s            :array[1..limit] of Tnode;
   n            :integer;

procedure init;
var
   x,y,bx,by    :extended;
   i            :integer;
begin
    read(bx,by,n);
    for i:=1 to n do
     with s[i] do
      begin
        read(x,y,id);
        x:=x-bx;y:=y-by;dig:=abs(y)/sqrt(x*x+y*y);
        if y>0 then
           if x>0 then dig:=1-dig
           else dig:=3+dig
        else if x>0 then dig:=1+dig
             else dig:=3-dig
      end;
end;

procedure sift(p,tot:integer);
var
   i,q          :integer;
   d            :extended;
begin
    i:=s[p].id;d:=s[p].dig;
    while true do
    begin
        q:=p+p;
        if (q<tot) and (s[q].dig<s[q+1].dig) then inc(q);
        if (q>tot) or (s[q].dig<d) then begin s[p].id:=i;s[p].dig:=d;exit;
                                        end;
        s[p]:=s[q];p:=q;
    end;
end;

procedure work;
var
   temp         :Tnode;
   i            :integer;
begin
    for i:=n div 2 downto 1 do sift(i,n);
    for i:=n downto 1 do
    begin
        temp:=s[i];
        s[i]:=s[1];
        s[1]:=temp;
        sift(1,i-1);
    end;
end;

procedure out;
var
   i            :integer;
begin
    writeln(0);
    for i:=1 to n do writeln(s[i].id);
    writeln(0);
end;

BEGIN
    init;
    work;
    out;
END.

My program:

Program t1173;{$N+}

Const Eps=1E-20;

Var Snail      :array[0..1000]of record X,Y,W :extended; ID :longint;
Use:boolean end;
    PredW,MinW :extended;
    i,N,CurI,j :longint;

Function GetW(CurX,CurY:extended):extended;
Var CurW,tgW,absW      :extended;
 begin
  if Abs(CurX)<Eps then begin
   if CurY>0 then CurW:=90;
   if CurY<=0 then CurW:=270;
  end else
  if Abs(CurY)<Eps then begin
   if CurX>0 then CurW:=0;
   if CurX<=0 then CurW:=180;
  end else begin
   tgW:=abs(CurY/CurX);
   absW:=ArcTan(tgW)*360/(2*Pi);
   if (CurX>0)and(CurY>0) then CurW:=absW else
   if (CurX>0)and(CurY<0) then CurW:=360-absW else
   if (CurX<0)and(CurY>0) then CurW:=180-absW else
   if (CurX<0)and(CurY<0) then CurW:=180+absW;
  end;
  GetW:=CurW;
 end;

begin
Snail[0].ID:=0;
Read(Snail[0].X,Snail[0].Y);
Read(N);
for i:=1 to N do Read(Snail[i].X,Snail[i].Y,Snail[i].ID);
for i:=1 to N do Snail[i].W:=GetW(Snail[i].X-Snail[0].X,Snail[i].Y-
Snail[0].Y);
for i:=1 to N do Snail[i].Use:=false;
PredW:=361;
Writeln(0);
for j:=1 to N do begin
 MinW:=-1;
 CurI:=0;
 for i:=1 to N do
  if not(Snail[i].Use) then
   if (Snail[i].W>MinW)and(PredW>Snail[i].W) then begin
    MinW:=Snail[i].W;
    CurI:=i;
   end;
 PredW:=MinW;
 Snail[CurI].Use:=true;
 Writeln(Snail[CurI].ID);
end;
Writeln(0);
end.

This is my program.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct
{
    long int x, y;
    int u, id;
} snail;

snail s[1001];
int d[1002];
int n, k;

int cmp_snail(const void *a, const void *b)
{
    snail *c = (snail *)a;
    snail *d = (snail *)b;

    if(c -> x == d -> x) return c -> y - d -> y;
    return c -> x - d -> x;
}

int main(void)
{
    int i;

    memset(s, 0, sizeof(s));
    scanf("%ld%ld", &s[0] . x, &s[0] . y); s[0] . id = 0;
    scanf("%d", &n);

    for(i = 1; i <= n; i ++)
    scanf("%ld%ld%d", &s[i] . x, &s[i] . y, &s[i] . id);

    qsort(s, n + 1, sizeof(snail), cmp_snail);

    d[0] = 0; k = 1;
    s[0] . u = 1;

    for(i = 1; i <= n; i ++)
    {
    int find = 1;
    d[k ++] = i;
    while(find && k > 2)
    {
        long int x1 = s[d[k - 3]] . x; long int y1 = s[d[k - 3]] . y;
        long int x2 = s[d[k - 2]] . x; long int y2 = s[d[k - 2]] . y;
        long int x  = s[d[k - 1]] . x; long int y  = s[d[k - 1]] . y;
        long int a = y1 - y2;
        long int b = x2 - x1;
        long int c = y2 * x1 - y1 * x2;
        long int v = a * x + b * y + c;

        if(v > 0)
        {
        d[k - 2] = d[k - 1];
        k --;
        } else if(v == 0)
        {
        printf("-1\n");
        return 0;
        } else find = 0;
    }
    }
    printf("k = %d; %d\n", k, s[0] . id);

    for(i = 0; i < k; i ++)
    s[d[i]] . u = 1;

    for(i = n; i >= 0; i --)
    if(!s[i] . u) d[k ++] = i;

    k = -1;
    for(i = 0; i <= n && k == -1; i ++)
    if(s[d[i]] . id == 0) k = i;

    for(i = 0; i <= n; i ++)
    {
    printf("%d\n", s[d[k]] . id);
    k ++;
    k %= n + 1;
    }
    printf("0\n");
}

I tested it using many random tests. I tested it usign GRX from djgpp
and all seemed OK. Why do I get WA?