### 11626 - Convex Hull

Posted:

**Fri Sep 04, 2009 2:35 am**Hello every one,i m getting WA in this problem, i m not sure about my process of sorting points according to angle.Pls help me,

Code: Select all

```
#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<string>
#include<algorithm>
#define pi 2*acos(0.0)
using namespace std;
struct point
{
double x,y;
};
point p[100005];
point ans[100005];
int cmp(const void *a,const void *b)
{
point *u=(point *)a;
point *v=(point *)b;
double theta1,theta2;
if((u->x-p[0].x)!=0)
{
theta1=atan((u->y-p[0].y)/(u->x-p[0].x));
if(theta1<0)
theta1=pi+theta1;
}
else theta1=pi/2;
if((v->x-p[0].x)!=0)
{theta2=atan((v->y-p[0].y)/(v->x-p[0].x));
if(theta2<0) theta2+=pi;
}
else theta2=pi/2;
if(theta1>theta2)
return 1;
else if(theta1<theta2)
return -1;
else
{
if((u->x-p[0].x)*(u->x-p[0].x)+(u->y-p[0].y)*(u->y-p[0].y)>(v->x-p[0].x)*(v->x-p[0].x)+(v->y-p[0].y)*(v->y-p[0].y))
return 1;
else if((u->x-p[0].x)*(u->x-p[0].x)+(u->y-p[0].y)*(u->y-p[0].y)<(v->x-p[0].x)*(v->x-p[0].x)+(v->y-p[0].y)*(v->y-p[0].y))
return -1;
else return 1;
}
}
int main()
{
long long int i,j,k,l,u,v,n,t,z;
string str1;
while(cin>>t)
{
for(z=1;z<=t;z++)
{
l=0;
cin>>n;
for(i=0;i<n;i++)
{
cin>>u>>v>>str1;
if(str1=="Y"){
p[l].x=u,p[l].y=v;
if(l>0)
ans[l-1].x=p[l].x,ans[l-1].y=p[l].y;
l++;}
}
for(i=1;i<l;i++)
{
if(p[i].x<p[0].x)
{swap(p[i],p[0]);
swap(ans[i-1],p[0]);
}
else if(p[i].x==p[0].x)
{
if(p[i].y<p[0].y)
{swap(p[i],p[0]);swap(ans[i-1],p[0]);}
}
}
cout<<l<<endl;
cout<<p[0].x<<" "<<p[0].y<<endl;
qsort(ans,l-1,sizeof(point),cmp);
for(i=0;i<l-1;i++)
cout<<ans[i].x<<" "<<ans[i].y<<endl;
}
}
return 0;
}
```