极角排序
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 #define maxn 30000 6 using namespace std; 7 8 struct point 9 { 10 double x,y; 11 int num; 12 }p[maxn]; 13 point pp; 14 double cross(const point &a,const point &b,const point &c) 15 { 16 return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x); 17 } 18 bool cmp(const point &a,const point &b) 19 { 20 if(cross(p[0],a,b)>0) return 0; 21 else return 1; 22 } 23 int main() 24 { 25 int n; 26 int k=0; 27 scanf("%d",&n); 28 for(int i=0; i<n; i++) 29 { 30 scanf("%lf%lf",&p[i].x,&p[i].y); 31 p[i].num=i+1; 32 if(p[i].y<p[k].y||(p[k].y==p[i].y&&p[i].x<p[k].x)) k=i; 33 } 34 swap(p[0],p[k]); 35 sort(p+1,p+n,cmp); 36 printf("%d %d ",p[0].num,p[n/2].num); 37 return 0; 38 }