Guest User

Untitled

a guest
Mar 28th, 2019
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.71 KB | None | 0 0
  1.     #include <bits/stdc++.h>
  2.      
  3.     using namespace std;
  4.      
  5.     const int N = 350, mod = 1e9 + 7;
  6.      
  7.     long long powmod(long long b, long long p) {
  8.       long long r = 1;
  9.       for (; p; p >>= 1, b = b * b % mod)
  10.         if (p &1)
  11.           r = r * b % mod;
  12.       return r;
  13.     }
  14.      
  15.     long long pw[N];
  16.      
  17.     typedef long long LD;
  18.     inline bool eq(LD a, LD b) { return a == b; }
  19.     inline bool lt(LD a, LD b) { return a < b; }
  20.     inline bool le(LD a, LD b) { return a <= b; }
  21.     inline int sign(LD x) { return eq(x, 0) ? 0 : (x < 0 ? -1 : 1); }
  22.      
  23.     struct point {
  24.       LD x, y;
  25.       point(LD x = 0, LD y = 0) : x(x), y(y) {}
  26.       point operator+(const point& p) const { return point(x+p.x, y+p.y); }
  27.       point operator-(const point& p) const { return point(x-p.x, y-p.y); }
  28.       point operator*(LD s) { return point(x*s, y*s); }
  29.       LD operator*(const point& p) const { return x*p.x + y*p.y; } // dot
  30.       LD operator%(const point& p) const { return x*p.y - y*p.x; } // cross
  31.       bool operator==(const point& p) const { return eq(x, p.x) && eq(y, p.y); }
  32.       bool operator<(const point& p) const { return eq(y, p.y) ? x < p.x : y < p.y; }
  33.     };
  34.     int ccw(point a, point b, point c) { return sign((b - a) % (c - b)); }
  35.     point ori;
  36.      
  37.     ostream& operator<<(ostream& os, point p) {
  38.       return os << "(" << p.x << "," <<p.y << ")";
  39.     }
  40.      
  41.     point vp[N];
  42.     int n, cnt[N][N];
  43.      
  44.     bool inside(point a, point p, point b) {
  45.       if (ccw(ori, a, b) < 0)
  46.         swap(a, b);
  47.       return ccw(ori, a, p) > 0 && ccw(a, b, p) > 0 && ccw(b, ori, p) > 0;
  48.     }
  49.     int triangle(int i, int j, int k) {
  50.       int ret = cnt[i][j] + cnt[j][k] + cnt[k][i];
  51.       ret = abs(ret);
  52.       if (inside(vp[i], vp[j], vp[k]) || inside(vp[i], vp[k], vp[j]) || inside(vp[j], vp[i], vp[k]))
  53.         --ret;
  54.       assert(ret >= 0);
  55.       return ret;
  56.     }
  57.      
  58.     long long calc(point pa, vector<pair<int, int>> &left, vector<pair<int, int>> &right) {
  59.       auto cmp = [&](pair<int, int> lef, pair<int, int> rig)->bool {
  60.         return sign((vp[lef.first] - pa) % (vp[rig.first] - pa)) < 0;
  61.       };
  62.       sort(left.begin(), left.end(), cmp);
  63.       sort(right.begin(), right.end(), cmp);
  64.       int i = 0;
  65.       long long cur = 0, ans = 0;
  66.       for (auto it : right) {
  67.         int id = it.first;
  68.         while (i < (int)left.size() && ccw(vp[id], pa, vp[left[i].first]) > 0) {
  69.           cur += left[i].second;
  70.           if (cur >= mod)
  71.             cur -= mod;
  72.           ++i;
  73.         }
  74.         ans = (ans + 1LL * cur * it.second) % mod;
  75.       }
  76.       if (ans < 0)
  77.         ans += mod;
  78.       return ans;
  79.     }
  80.      
  81.     void solve() {
  82.       pw[0] = 1;
  83.       for (int i = 1; i < N; ++i) {
  84.         pw[i] = (pw[i-1] * 2LL) % mod;
  85.       }
  86.       scanf("%d", &n);
  87.       for (int i = 0; i < n; ++i) {
  88.         int x, y;
  89.         scanf("%d %d", &x, &y);
  90.         vp[i] = point(x, y);
  91.       }
  92.       for (int i = 1; i < n; ++i) {
  93.         if (vp[i] < vp[0])
  94.           swap(vp[0], vp[i]);
  95.       }
  96.       for (int i = 1; i < n; ++i) {
  97.         vp[i] = vp[i] - vp[0];
  98.       }
  99.       vp[0] = vp[0] - vp[0];
  100.       memset(cnt, 0, sizeof cnt);
  101.       for (int i = 1; i < n; ++i) {
  102.         for (int j = i+1; j < n; ++j) {
  103.           for (int k = 1; k < n; ++k) {
  104.             if (k == i || k == j) continue;
  105.             cnt[i][j] += inside(vp[i], vp[k], vp[j]);
  106.           }
  107.           cnt[j][i] = cnt[i][j];
  108.           if (ccw(ori, vp[i], vp[j]) > 0)
  109.             cnt[j][i] *= -1;
  110.           else
  111.             cnt[i][j] *= -1;
  112.         }
  113.       }
  114.       long long ans = 0;
  115.       for (int a = 0; a < n; ++a) {
  116.         point pa = vp[a];
  117.         for (int b = a+1; b < n; ++b) {
  118.           point pb = vp[b];
  119.           vector<pair<int, int>> left, right;
  120.           for (int k = 0; k < n; ++k) {
  121.             if (k == a || k == b) continue;
  122.             if (ccw(pa, pb, vp[k]) > 0)
  123.               left.emplace_back(k, pw[triangle(a, b, k)]);
  124.             else
  125.               right.emplace_back(k, pw[triangle(a, b, k)]);
  126.           }
  127.           long long sum_left = 0, sum_right = 0;
  128.           for (auto it : left)
  129.             sum_left += it.second;
  130.           for (auto it : right)
  131.             sum_right += it.second;
  132.           sum_right %= mod;
  133.           sum_left %= mod;
  134.           ans = (ans + 1LL * sum_left * sum_right) % mod;
  135.           ans = (ans - calc(pa, left, right) - calc(pb, right, left)) % mod;
  136.           if (ans < 0) ans += mod;
  137.         }
  138.       }
  139.       ans = (ans * powmod(2, mod - 2)) % mod;
  140.       if (ans < 0) ans += mod;
  141.       printf("%lld\n", ans);
  142.     }
  143.      
  144.     int main() {
  145.       int tt = 1;
  146.       while (tt--) {
  147.         solve();
  148.       }
  149.       return 0;
  150.     }
Add Comment
Please, Sign In to add comment