Advertisement
Guest User

Untitled

a guest
Feb 28th, 2015
190
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.88 KB | None | 0 0
  1. #include <iostream>
  2. #include <sstream>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <string>
  6. #include <string.h>
  7. #include <cstdio>
  8. #include <vector>
  9. #include <map>
  10. #include <set>
  11. #include <cstring>
  12. #include <queue>
  13. #include <bitset>
  14.  
  15.  
  16. using namespace std;
  17.  
  18.  
  19. #define eps 0.000001
  20. #define Pi acos(-1)
  21.  
  22.  
  23. struct point{
  24.     double x, y;
  25.     point(){}
  26.     point(double _x, double _y) {
  27.         x = _x;
  28.         y = _y;
  29.     }
  30. };
  31.  
  32.  
  33. int n;
  34. point p[200000];
  35.  
  36.  
  37. double vec(point a, point b) {
  38.     return a.x * b.y - a.y * b.x;
  39. }
  40.  
  41.  
  42. bool operator <(const point a, const point b) {
  43.     return atan2(a.y, a.x) < atan2(b.y, b.x);
  44. }
  45.  
  46.  
  47. long long l[200000], r[200000];
  48. long long d[200000];
  49.  
  50.  
  51. int main() {
  52. //  freopen("tricount.in", "r", stdin);freopen("tricount.out", "w", stdout);
  53.     cin >> n;
  54.     for (int i = 0; i < n; i++) {
  55.         scanf("%lf %lf", &p[i].x, &p[i].y);
  56.     }
  57.     if (n == 5) {
  58. //      cout << 5 << endl;
  59. //      return 0;
  60.     }
  61.     sort(p, p + n);
  62.     for (int i = n; i < 2 * n; i++) {
  63.     //  cout << p[i - n].x << ' ' << p[i - n].y << endl;
  64.         p[i] = p[i - n];   
  65.     }
  66.     int r1 = 0;
  67.     for (int i = 0; i < n; i++) {
  68.         r1 = max(r1, i);
  69.         while (r1 - i < n - 1 && abs(atan2(p[r1 + 1].y, p[r1 + 1].x) - atan2(p[i].y, p[i].x)) < Pi) {
  70.             r1++;
  71.         }
  72.         r[i] = r1 - i;
  73.         r[i + n] = r[i];
  74.         //cout << r[i] << endl;
  75.         d[i] = (i > 0 ? d[i - 1]: 0) + r[i];
  76.     }
  77.     for (int i = 0; i < n; i++) {
  78.         d[i + n] = d[i + n - 1] + r[i];
  79.     }
  80.     int l1 = 2 * n - 1;
  81.     for (int i = 2 * n - 1; i >= n; i--) {
  82.         l1 = min(l1, i);
  83.         while (i - l1 < n - 1 && abs(atan2(p[l1 - 1].y, p[l1 - 1].x) - atan2(p[i].y, p[i].x)) < Pi) {
  84.             l1--;
  85.         }
  86.         l[i] = i - l1;
  87.         l[i - n] = l[i];
  88.         //cout << l[i] << endl;
  89.     }
  90.     //cout << "popka" << endl;
  91.     long long k = 0;
  92.     long long ans = 0;
  93.     for (long long i = 0; i < n; i++) {
  94.         //cout << i << endl;
  95.         k = max(k, (long long)i + 1);
  96.         while (k <= i + r[i]) {
  97.             int t = k + r[k];
  98.             if (t >= n) {
  99.                 t -= (t / n) * n;
  100.             }
  101.             int t1 = i - l[i + n];
  102.             if (t1 < 0) {
  103.                 t1 = n + t1 - 1;
  104.             }
  105.         //  cout << t << endl;
  106.             if (t >= t1) {
  107.                 break;
  108.             }
  109.             k++;
  110.         }
  111.         if (k > i + r[i]) {
  112.             continue;
  113.         }
  114.         long long t1 = i - l[i + n];
  115.         if (t1 < 0) {
  116.             t1 = n + t1 - 1;
  117.         }
  118.         //cout << k << endl;
  119.         long long k1 = k;
  120.         if (k1 >= n) {
  121.             k1 -= n;
  122.         }
  123.         if (k >= n && t1 < n) {
  124.             t1 += n;
  125.         }
  126.         long long k2 = k;
  127.         if (i + r[i] >= n && k < n) {
  128.             k2 += n;
  129.         }
  130.         long long t2 = t1;
  131.         if (i + r[i] >= n && t1 < n) {
  132.             t2 += n;
  133.         }
  134.         long long p = 0;
  135.         if (i + r[i] < n && k >= n) {
  136.             p += n;
  137.         }
  138.         long long s = max(0LL, r[k] - k + t1 - (min(i + r[i] + p, i - 1LL + n) - k2 + 1));
  139.     //  cout << s << endl;
  140.       // cout << d[min(i + r[i], i - 1LL + n)] - (k > 0 && k != n ? d[k - 1]: 0) << endl;
  141.         ans += d[min(i + r[i] + p, i - 1LL + n)] - (k > 0 && k != n ? d[k - 1]: 0) - (abs(r[k] - k + t1) * (abs(r[k] - k + t1) + 1)) / 2 + (s * (s + 1)) / 2;
  142.     }
  143.     cout << ans << endl;
  144.     return 0;
  145. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement