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