tcbpg

Untitled

Aug 12th, 2011
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.06 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 & l){
  49.     VP res = l; if(l.size() < 3) return res;
  50.     r = *(min_element(res.begin(), res.end(), men2));
  51.     sort(res.begin(), res.end());
  52.  
  53.     tint i = 0; VP ch; ch.push_back(res[i++]); ch.push_back(res[i++]);
  54.     while(i < res.size()){
  55.         if(ch.size() > 1 && area3(ch[ch.size()-2], ch[ch.size()-1], res[i]) <= 0)
  56.             ch.pop_back();
  57.         else
  58.             ch.push_back(res[i++]);
  59.     }
  60.  
  61.     return ch;
  62. }
  63.  
  64. int main(){
  65. #ifdef ACM
  66.     freopen("test.in", "r", stdin);
  67. #endif
  68.  
  69.     int N; scanf("%d", &N);
  70.     while(N != 0){
  71.         int L = 0;
  72.         VP v;
  73.  
  74.         forn(i, N){
  75.             int x, y; scanf("%d %d", &x, &y);
  76.             v.push_back(pto(x, y));
  77.         }
  78.  
  79.         while(v.size() > 0){
  80.             VP ch = chull(v);
  81.             VP tmp(v.size());
  82.  
  83.             sort(ch.begin(), ch.end(), men2);
  84.             sort(v.begin(), v.end(), men2);
  85.  
  86.             VP::iterator it = set_difference(v.begin(), v.end(), ch.begin(), ch.end(), tmp.begin(), men2);
  87.  
  88.             tmp.resize(it - tmp.begin());
  89.  
  90.             v.clear();
  91.             v = tmp;
  92.  
  93.             L++;
  94.         }
  95.  
  96.         if(L % 2 == 0) puts("Do not take this onion to the lab!"); else puts("Take this onion to the lab!");
  97.         scanf("%d", &N);
  98.     }
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment