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 1173. Lazy Snail

It seems to me that either test incorrect or checker is invalid
Posted by Krayev Alexey(PSU-Again) 11 Aug 2005 19:26
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