ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
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