tcbpg

Untitled

Aug 12th, 2011
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.12 KB | None | 0 0
  1. //LiveArchive 3655 Onion Layers - TCBPG
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <vector>
  8.  
  9. using namespace std;
  10.  
  11. #define forn(i, n) for(int i = 0; i < (int) (n); i++)
  12. #define forsn(i, s, n) for(int i = (s); i < (int) (n); i++)
  13.  
  14. typedef long long tint;
  15.  
  16. inline int sqr(int x){ return x*x; }
  17.  
  18. int pcruz(int x1, int y1, int x2, int y2){ return x1*y2-x2*y1; }
  19. struct pto{
  20.     int x,y;
  21.     int n2(pto &p2) const { return sqr(x-p2.x) + sqr(y-p2.y); };
  22.  
  23.     pto(int u, int v){ x = u, y = v; };
  24.     pto(){};
  25. } r;
  26.  
  27. int area3(pto a, pto b, pto c){ return pcruz(b.x-a.x, b.y-a.y, c.x-a.x, c.y-a.y); }
  28.  
  29. bool men2(const pto&p1, const pto&p2){
  30.     return (p1.y == p2.y) ? (p1.x < p2.x) : (p1.y < p2.y);
  31. }
  32.  
  33. bool orden(const pto & p1, const pto & p2){
  34.     return (p1.x == p2.x) ? (p1.y < p2.y) : (p1.x < p2.x);
  35. }
  36.  
  37. bool operator<(const pto &p1, const pto&p2){
  38.     int ar = area3(r, p1, p2);
  39.     return (ar == 0) ? (p1.n2(r) < p2.n2(r)) : ar>0;
  40. }
  41.  
  42. bool operator==(const pto& p1, const pto & p2){
  43.     return (p1.x == p2.x && p1.y == p2.y);
  44. }
  45.  
  46. typedef vector<pto> VP;
  47.  
  48. VP chull(VP & P){
  49.     int n = P.size(), k = 0;
  50.     vector<pto> H(2*n);
  51.  
  52.     // Sort Points lexicographically
  53.     sort(P.begin(), P.end(), men2);
  54.  
  55.     // Build lower hull
  56.     for (int i = 0; i < n; i++) {
  57.     while (k >= 2 && area3(H[k-2], H[k-1], P[i]) < 0){
  58.     k--;
  59.     }
  60.     H[k++] = P[i];
  61.     }
  62.  
  63.     // Build upper hull
  64.     for (int i = n-2, t = k+1; i >= 0; i--) {
  65.     while (k >= t && area3(H[k-2], H[k-1], P[i]) < 0){
  66.     k--;
  67.     }
  68.     H[k++] = P[i];
  69.     }
  70.  
  71.     H.resize(k);
  72.  
  73.     return H;
  74. }
  75.  
  76. int main(){
  77. #ifdef ACM
  78.     freopen("test.in", "r", stdin);
  79. #endif
  80.  
  81.     int N; scanf("%d", &N);
  82.     while(N != 0){
  83.         int L = 0;
  84.         VP v;
  85.  
  86.         forn(i, N){
  87.             int x, y; scanf("%d %d", &x, &y);
  88.             v.push_back(pto(x, y));
  89.         }
  90.  
  91.         while(v.size() > 0){
  92.             VP ch = chull(v);
  93.             VP tmp(v.size());
  94.  
  95.             sort(ch.begin(), ch.end(), men2);
  96.             sort(v.begin(), v.end(), men2);
  97.  
  98.             VP::iterator it = set_difference(v.begin(), v.end(), ch.begin(), ch.end(), tmp.begin(), men2);
  99.  
  100.             tmp.resize(it - tmp.begin());
  101.  
  102.             v.clear();
  103.             v = tmp;
  104.  
  105.             L++;
  106.         }
  107.  
  108.         if(L % 2 == 0) puts("Do not take this onion to the lab!"); else puts("Take this onion to the lab!");
  109.         scanf("%d", &N);
  110.     }
  111.     return 0;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment