Advertisement
Guest User

Untitled

a guest
Apr 30th, 2017
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.17 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <cstdio>
  6. #include <queue>
  7. #include <cassert>
  8. #include <map>
  9. #include <string>
  10. #include <iomanip>
  11. #include <set>
  12. #include <unordered_set>
  13. #include <queue>
  14. #include <unordered_map>
  15. #include <ctime>
  16. #include <vector>
  17. #include <bitset>
  18. using namespace std;
  19.  
  20. #define debug(x) cerr << #x << " = " << x << endl
  21. #define FOR(i, n) for (int i = 0; i < (int)(n); ++i)
  22. #define pb push_back
  23. #define sz(v) (int)(v).size()
  24. #define mp make_pair
  25. #define all(v) (v).begin(), (v).end()
  26. #define for1(i,n) for(int i = 1; i <= (int)(n); ++ i)
  27. #define ford1(i,n) for(int i = (int)(n); i >= 1; -- i)
  28. #define ford(i,n) for(int i = (int)(n)-1; i >= 0; -- i)
  29. #define forn(i,n) for(int i = 0; i < (int)(n); ++ i)
  30. typedef vector<int> vi;
  31. typedef vector<pair<int, int> > vpi;
  32. typedef pair<int, int> pii;
  33. // typedef long long LL;
  34. typedef long double LD;
  35.  
  36. const int INF = 2e6;
  37. const int N = 50007;
  38. const LD eps = 1e-8;
  39.  
  40. struct pt {
  41.     LD x, y;
  42.     pt (LD x=0, LD y=0): x(x), y(y) {
  43.     }
  44.    
  45.     void read() {
  46.         int a, b;
  47.         scanf("%d%d", &a, &b);
  48.         x=a;
  49.         y=b;
  50.     }
  51.    
  52.     pt operator + (const pt &o) const {
  53.         return pt(x+o.x, y+o.y);
  54.     }
  55.    
  56.     pt operator - (const pt &o) const {
  57.         return pt(x-o.x, y-o.y);
  58.     }
  59.    
  60. } p[N];
  61. int n;
  62.  
  63. struct Plane {
  64.     LD a, b, c;
  65.     int s;
  66.    
  67.     Plane(LD aa=0, LD bb=0, LD cc=0, int s=0): s(s) {
  68.         LD norm = sqrtl(aa*aa+bb*bb);
  69.         a = aa / norm;
  70.         b = bb / norm;
  71.         c = cc / norm;
  72.     }
  73. };
  74.  
  75. LD dot(pt u, pt v) {
  76.     return u.x * v.x + u.y * v.y;
  77. }
  78.  
  79. LD sign(LD x) {
  80.     if (x < -eps) return -1;
  81.     if (x > +eps) return 1;
  82.     return 0;
  83. }
  84.  
  85. int get_sign(pt A, Plane p) {
  86.     return sign(p.a * A.x + p.b * A.y + p.c);
  87. }
  88.  
  89. struct HalfPlaneIntersection {
  90.    
  91.     vector<Plane> planes;
  92.    
  93.     void init() {
  94.         planes.clear();
  95.         planes.resize(0);
  96.     }
  97.    
  98.     void add(Plane p) {
  99.         if (p.s == 1) {
  100.             p.c -= eps;
  101.         }
  102.         else {
  103.             p.c += eps;
  104.         }
  105.         planes.pb(p);
  106.     }
  107.    
  108.     bool check() {
  109.         random_shuffle(all(planes));
  110.         planes.pb(Plane(1, 0, INF, 1));
  111.         planes.pb(Plane(1, 0, -INF, -1));
  112.         planes.pb(Plane(0, 1, INF, 1));
  113.         planes.pb(Plane(0, 1, -INF, -1));
  114.         reverse(all(planes));
  115.        
  116.         pt cur(-INF, 0);
  117.         for (int iter = 4; iter < sz(planes); ++iter) {
  118.             auto p = planes[iter];
  119.            
  120.             if (get_sign(cur, p) == -p.s) {
  121.                 pt dir = pt(-p.b, p.a);
  122.                 vector<pt> A, B;
  123.                
  124.                 FOR(i, iter) {
  125.                     auto q = planes[i];
  126.                    
  127.                     LD det = p.a * q.b - p.b * q.a;
  128.                     if (fabsl(det) < eps) continue;
  129.                     LD detx = q.c * p.b - p.c * q.b;
  130.                     LD dety = p.c * q.a - q.c * p.a;
  131.                     pt X = pt(detx/det, dety/det);
  132.                    
  133.                     if (get_sign(X + dir, q) == q.s) {
  134.                         A.pb(X);
  135.                     }
  136.                     else {
  137.                         B.pb(X);
  138.                     }
  139.                 }
  140.                
  141.                 // A and B are not empty (note 4 initial half planes)
  142.                 pt amax = A[0];
  143.                 for (auto P : A) {
  144.                     if (dot(P, dir) > dot(amax, dir)) amax = P;
  145.                 }
  146.                
  147.                 pt bmax = B[0];
  148.                 for (auto P : B) {
  149.                     if (dot(P, dir) < dot(bmax, dir)) bmax = P;
  150.                 }
  151.                
  152.                 if (amax.x < bmax.x) cur = amax;
  153.                 else cur = bmax;
  154.                
  155.                 FOR(i, iter+1) {
  156.                     if (get_sign(cur, planes[i]) == -planes[i].s) return false;
  157.                 }
  158.             }
  159.         }
  160.        
  161.         return true;
  162.     }
  163.    
  164. } hp;
  165.  
  166.  
  167. bool check(int k) {
  168.     hp.init();
  169.     FOR(i, n) {
  170.         int j=(i+k)%n;
  171.        
  172.         LD a = p[i].y - p[j].y;
  173.         LD b = p[j].x - p[i].x;
  174.         LD c = -a * p[i].x - b * p[i].y;
  175.        
  176.         int z=(i-1+n)%n;
  177.         int s = sign(a*p[z].x + b*p[z].y + c);
  178.        
  179.         hp.add(Plane(a, b, c, s));
  180.     }
  181.     return hp.check();
  182. }
  183.  
  184. void solve() {
  185.     scanf("%d", &n);
  186.     FOR(i, n) {
  187.         p[i].read();
  188.     }
  189.    
  190.     int l = 1;
  191.     int r = n-2;
  192.     while(l < r) {
  193.         int m = (l+r+1)/2;
  194.         if (check(m)) l = m;
  195.         else r=m-1;
  196.     }
  197.    
  198.     printf("%d\n", l);
  199. }
  200.  
  201. void testgen() {
  202.     FILE *f = fopen("input.txt", "w");
  203.     // srand(time(0));
  204.     fclose(f);
  205. }
  206.  
  207. int  main(int argc, char* argv[]) {
  208. #ifdef harhro94
  209.     // testgen();
  210.     freopen("input.txt", "r", stdin);
  211.     // freopen("output.txt", "w", stdout);
  212. #else
  213. #define task "jungle"
  214.     freopen(task".in", "r", stdin);
  215.     freopen(task".out", "w", stdout);
  216. #endif
  217.  
  218.     solve();
  219.  
  220. #ifdef harhro94
  221.     cerr << "\ntime = " << clock() / (double)CLOCKS_PER_SEC << endl;
  222. #endif
  223.     return 0;
  224. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement