yeputons

Untitled

Jul 11th, 2012
184
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.28 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <cassert>
  6. #include <algorithm>
  7. #include <string>
  8. #include <vector>
  9. #include <deque>
  10. #include <queue>
  11. #include <map>
  12. #include <set>
  13.  
  14. using namespace std;
  15.  
  16. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  17. #define pb push_back
  18. #define mp make_pair
  19. #define sz(x) ((int)(x).size())
  20.  
  21. typedef long long ll;
  22. typedef vector<ll> vll;
  23. typedef vector<int> vi;
  24. typedef vector<vi> vvi;
  25. typedef vector<bool> vb;
  26. typedef vector<vb> vvb;
  27. typedef pair<int, int> pii;
  28.  
  29. int sgn(ll x) { return x < 0 ? -1 : !!x; }
  30. struct pt {
  31.   int x, y, id, id0;
  32.   pt() : x(0), y(0) {}
  33.   pt(int _x, int _y) : x(_x), y(_y) {}
  34.   pt operator-(const pt &p2) const { return pt(x - p2.x, y - p2.y); }
  35.   ll operator*(const pt &p2) const { return ll(x) * p2.y - ll(y) * p2.x; }
  36.   ll dist2() const { return ll(x) * x + ll(y) * y; }
  37. };
  38.  
  39. bool rcmp(const pt &a, const pt &b) { if (a * b) return a * b > 0; return a.dist2() < b.dist2(); }
  40. bool icmp(const pt &a, const pt &b) { return a.id < b.id; }
  41. bool cross(pt a1, pt b1, pt a2, pt b2) {
  42.   if ( sgn((a2 - a1) * (b1 - a1)) * sgn((b2 - a1) * (b1 - a1)) > 0) return false;
  43.   swap(a1, a2);
  44.   swap(b1, b2);
  45.   if ( sgn((a2 - a1) * (b1 - a1)) * sgn((b2 - a1) * (b1 - a1)) > 0) return false;
  46.   return true;
  47. }
  48.  
  49. bool is_in(int l, int r, int x) {
  50.   if (l > r) swap(l, r);
  51.   return l <= x && x <= r;
  52. }
  53. bool contains(pt a, pt b, pt p) {
  54.   if ((b - a) * (p - a)) return false;
  55.   return is_in(a.x, b.x, p.x) && is_in(a.y, b.y, p.y);
  56. }
  57.  
  58. int main() {
  59.   #ifdef DEBUG
  60.   freopen("std.in", "r", stdin);
  61.   freopen("std.out", "w", stdout);
  62.   #endif
  63.  
  64.   int n;
  65.   while (scanf("%d", &n) >= 1) {
  66.     vector<pt> pts(n);
  67.     for (int i = 0; i < n; i++)
  68.       scanf("%d%d", &pts[i].x, &pts[i].y), pts[i].id = i + 1;
  69.  
  70.     if (n <= 1000) {
  71.       vi res;
  72.       for (int i = 0; i < n; i++) {
  73.         bool g = true;
  74.         pt p = pts[i];
  75.  
  76.         for (int i2 = 0; i2 < n; i2++) {
  77.           if (i2 != i)
  78.             if (contains(pt(), p, pts[i2])) g = false;
  79.  
  80.           int i3 = i2 + 1; if (i3 == n) i3 = 0;
  81.           if (i2 == i || i3 == i) continue;
  82.  
  83.           pt a = pts[i2], b = pts[i3];
  84.           if (cross(a, b, pt(), p)) g = false;
  85.         }
  86.         if (g) res.pb(i);
  87.       }
  88.  
  89.       printf("%d\n", sz(res));
  90.       for (int i = 0; i < sz(res); i++) {
  91.         if (i) printf(" ");
  92.         printf("%d", res[i] + 1);
  93.       }
  94.       printf("\n");
  95.       continue;
  96.     }
  97.  
  98.     {
  99.       ll sq = 0;
  100.       for (int i = 0; i < n; i++) {
  101.         int ne = i + 1; if (ne >= n) ne = 0;
  102.         sq += pts[i] * pts[ne];
  103.       }
  104.       if (sq > 0)
  105.         reverse(pts.begin(), pts.end());
  106.     }
  107.  
  108.     rotate(pts.begin(), min_element(pts.begin(), pts.end(), rcmp), pts.end());
  109.     for (int i = 0; i < sz(pts); i++)
  110.       pts[i].id0 = i;
  111.  
  112.     vector<pt> res;
  113.     res.pb(pts[0]);
  114.  
  115.     bool mode = true;
  116.  
  117.     for (int i = 1; i < sz(pts); i++) {
  118.       bool g = true;
  119.       int delMode = -1;
  120.       while (!res.empty()) {
  121.         pt pr = res.back(), cur = pts[i];
  122.         if (pr * cur > 0) {
  123.           break;
  124.         }
  125.         if (!mode) {
  126.           g = false;
  127.           break;
  128.         }
  129.         if (pr * cur == 0) {
  130.           if (cur.dist2() < pr.dist2()) {
  131.             res.pop_back();
  132.             assert(res.empty() || res.back() * cur > 0);
  133.             continue;
  134.           } else {
  135.             g = false;
  136.             break;
  137.           }
  138.         }
  139.  
  140.         if (delMode < 0) {
  141.           assert(pr.id0 >= 1);
  142. //          pt pr2 = res[sz(res) - 2];
  143.           pt pr2 = pts[pr.id0 - 1];
  144. //          eprintf("%d %d %d\n", pr2.id, pr.id, cur.id);
  145.           delMode = (pr * pr2 < 0);
  146.           delMode = delMode && ((pr2 - pr) * (cur - pr) > 0);
  147.           delMode = !delMode;
  148. //          delMode = ((pr - pr2) * (cur - pr2)) > 0;
  149. //          delMode = delMode && (pr * pr2 < 0);
  150. //          eprintf("delMode=%d\n", delMode);
  151.           if (!delMode) { g = false; break; }
  152.         }
  153.         res.pop_back();
  154.       }
  155.       if (g)
  156.         res.pb(pts[i]);
  157.       mode = g;
  158.     }
  159.  
  160.     sort(res.begin(), res.end(), icmp);
  161.     printf("%d\n", sz(res));
  162.     for (int i = 0; i < sz(res); i++) {
  163.       if (i) printf(" ");
  164.       printf("%d", res[i].id);
  165.     }
  166.     printf("\n");
  167. //    break;
  168.   }
  169.   return 0;
  170. }
Add Comment
Please, Sign In to add comment