Advertisement
nasarouf

Sorting angles

Apr 17th, 2015
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. //sorting by angles of integer vectors
  2. //nasarouf@cs.ubc.ca
  3.  
  4. #define X first
  5. #define Y second
  6. const double PI=(2*acos(0.0f));
  7. typedef long long Long;
  8. typedef pair<int,int> PII;
  9. PII p[MAX],q[MAX];
  10. int n;
  11. #define LEN(a,b) ((Long)(a)*(a)+(Long)(b)*(b))
  12.  
  13. bool parallel(const PII& a, const PII &b){
  14.     if ((Long)a.X*b.X<0) return false;
  15.     if (a.X==0 && b.X==0) return ((Long)a.Y*b.Y>0);
  16.     return ((Long)a.X*b.Y == (Long) a.Y*b.X);
  17. }
  18.  
  19. int cmp(const void *pa, const void* pb){
  20.     const PII *a=(const PII*)pa;
  21.     const PII *b=(const PII*)pb;
  22.     if (!parallel(*a, *b)){
  23.         double A=atan2((double)a->second,(double)a->first), B=atan2((double)b->second,(double)b->first);
  24.         if (A<0) A+=2*PI;
  25.         if (B<0) B+=2*PI;
  26.         if (A<B) return -1;
  27.         return 1;
  28.     }
  29.     if (LEN(a->first,a->second)<LEN(b->first,b->second)) return -1;
  30.     //if (LEN(a->first,a->second)>LEN(b->first,b->second)) return 1;
  31.     //if ((Long)a->first*b->second==(Long)a->second*b->first) return 0;
  32.     //return 0;
  33.     return 1;
  34. }
  35.  
  36. Long dot(PII& a, PII &b){
  37.     return (Long)a.X*b.X+(Long)a.Y*b.Y;
  38. }
  39.  
  40. //
  41. //
  42. qsort(q,n-1,sizeof(q[0]),cmp);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement