nasarouf

Sorting angles

Apr 17th, 2015
150
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.  
  3. #define X first
  4. #define Y second
  5. const double PI=(2*acos(0.0f));
  6. typedef long long Long;
  7. typedef pair<int,int> PII;
  8. PII p[MAX],q[MAX];
  9. int n;
  10. #define LEN(a,b) ((Long)(a)*(a)+(Long)(b)*(b))
  11.  
  12. bool parallel(const PII& a, const PII &b){
  13.     if ((Long)a.X*b.X<0) return false;
  14.     if (a.X==0 && b.X==0) return ((Long)a.Y*b.Y>0);
  15.     return ((Long)a.X*b.Y == (Long) a.Y*b.X);
  16. }
  17.  
  18. int cmp(const void *pa, const void* pb){
  19.     const PII *a=(const PII*)pa;
  20.     const PII *b=(const PII*)pb;
  21.     if (!parallel(*a, *b)){
  22.         double A=atan2((double)a->second,(double)a->first), B=atan2((double)b->second,(double)b->first);
  23.         if (A<0) A+=2*PI;
  24.         if (B<0) B+=2*PI;
  25.         if (A<B) return -1;
  26.         return 1;
  27.     }
  28.     if (LEN(a->first,a->second)<LEN(b->first,b->second)) return -1;
  29.     //if (LEN(a->first,a->second)>LEN(b->first,b->second)) return 1;
  30.     //if ((Long)a->first*b->second==(Long)a->second*b->first) return 0;
  31.     //return 0;
  32.     return 1;
  33. }
  34.  
  35. Long dot(PII& a, PII &b){
  36.     return (Long)a.X*b.X+(Long)a.Y*b.Y;
  37. }
  38.  
  39. //
  40. //
  41. qsort(q,n-1,sizeof(q[0]),cmp);
Advertisement
Add Comment
Please, Sign In to add comment