Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //sorting by angles of integer vectors
- //nasarouf@cs.ubc.ca
- #define X first
- #define Y second
- const double PI=(2*acos(0.0f));
- typedef long long Long;
- typedef pair<int,int> PII;
- PII p[MAX],q[MAX];
- int n;
- #define LEN(a,b) ((Long)(a)*(a)+(Long)(b)*(b))
- bool parallel(const PII& a, const PII &b){
- if ((Long)a.X*b.X<0) return false;
- if (a.X==0 && b.X==0) return ((Long)a.Y*b.Y>0);
- return ((Long)a.X*b.Y == (Long) a.Y*b.X);
- }
- int cmp(const void *pa, const void* pb){
- const PII *a=(const PII*)pa;
- const PII *b=(const PII*)pb;
- if (!parallel(*a, *b)){
- double A=atan2((double)a->second,(double)a->first), B=atan2((double)b->second,(double)b->first);
- if (A<0) A+=2*PI;
- if (B<0) B+=2*PI;
- if (A<B) return -1;
- return 1;
- }
- if (LEN(a->first,a->second)<LEN(b->first,b->second)) return -1;
- //if (LEN(a->first,a->second)>LEN(b->first,b->second)) return 1;
- //if ((Long)a->first*b->second==(Long)a->second*b->first) return 0;
- //return 0;
- return 1;
- }
- Long dot(PII& a, PII &b){
- return (Long)a.X*b.X+(Long)a.Y*b.Y;
- }
- //
- //
- qsort(q,n-1,sizeof(q[0]),cmp);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement