EntropyIncreaser

tran

Apr 8th, 2019
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.43 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstring>
  3.  
  4. #include <algorithm>
  5. #include <numeric>
  6. #include <vector>
  7.  
  8. #define LOG(FMT...) fprintf(stderr, FMT)
  9.  
  10. using namespace std;
  11.  
  12. typedef long long ll;
  13. typedef pair<ll, pair<ll, ll> > Line;
  14.  
  15. struct Vec {
  16.   ll x, y;
  17.  
  18.   Vec(ll x = 0, ll y = 0) : x(x), y(y) {}
  19.  
  20.   Vec operator+(const Vec& rhs) const { return Vec(x + rhs.x, y + rhs.y); }
  21.   Vec operator-() const { return Vec(-x, -y); }
  22.   Vec operator-(const Vec& rhs) const { return *this - rhs; }
  23.   ll operator^(const Vec& rhs) const { return x * rhs.x + y * rhs.y; }
  24.   ll operator*(const Vec& rhs) const { return x * rhs.y - y * rhs.x; }
  25.  
  26.   bool operator<(const Vec& rhs) const;
  27.   bool operator==(const Vec& rhs) const { return *this * rhs == 0; }
  28. };
  29.  
  30. const int N = 1010;
  31.  
  32. int n, m;
  33. int x[N], y[N];
  34. int c1[N][N], c2[N][N];
  35. Line uline[N * N];
  36. pair<Vec, int> cyc[N];
  37. Vec ve[N], pl[N * 3];
  38. vector<ll> shade[N * N];
  39.  
  40. #define C first
  41. #define A second.first
  42. #define B second.second
  43.  
  44. ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
  45.  
  46. Line norm(const Line& line) {
  47.   ll a = line.A, b = line.B, c = line.C;
  48.   ll g = gcd(gcd(a, b), c);
  49.   a /= g;
  50.   b /= g;
  51.   c /= g;
  52.   if (c < 0) {
  53.     a = -a;
  54.     b = -b;
  55.     c = -c;
  56.   }
  57.   return make_pair(c, make_pair(a, b));
  58. }
  59.  
  60. Line norm(int x1, int y1, int x2, int y2) {
  61.   int dx = x2 - x1, dy = y2 - y1;
  62.   ll a = dy, b = -dx, c = dx * (ll)y1 - dy * (ll)x1;
  63.   return norm(make_pair(c, make_pair(a, b)));
  64. }
  65.  
  66. int gid(const Line& line) { return lower_bound(uline + 1, uline + m + 1, line) - uline; }
  67.  
  68. int gr(const Vec& v) {
  69.   LOG("REG %lld %lld\n", v.x, v.y);
  70.   if (v.y == 0)
  71.     return v.x < 0;
  72.   return y < 0;
  73. }
  74.  
  75. bool Vec::operator<(const Vec& rhs) const {
  76.   int r1 = gr(*this), r2 = gr(rhs);
  77.   if (r1 != r2)
  78.     return r1 < r2;
  79.   return *this * rhs > 0;
  80. }
  81.  
  82. int main() {
  83.   scanf("%d", &n);
  84.   for (int i = 1; i <= n; ++i)
  85.     scanf("%d%d", &x[i], &y[i]);
  86.   for (int i = 1; i <= n; ++i)
  87.     for (int j = 1; j < i; ++j)
  88.       uline[++m] = norm(x[i], y[i], x[j], y[j]);
  89.   sort(uline + 1, uline + m + 1);
  90.   m = unique(uline + 1, uline + m + 1) - uline - 1;
  91.   for (int i = 1; i <= n; ++i)
  92.     for (int j = 1; j < i; ++j) {
  93.       // k = -dx/dy
  94.       // 2dyy-dy(y1+y2)=-2dxx+dx(x1+x2)
  95.       // 2dxx+2dyy-dy(y1+y2)-dx(x1+x2)
  96.       int x1 = x[i], y1 = y[i], x2 = x[j], y2 = y[j];
  97.       int dy = y2 - y1, dx = x2 - x1;
  98.       Line cur = norm(make_pair(-dy * (ll)(y1 + y2) - dx * (ll)(x1 + x2), make_pair(2LL * dx, 2LL * dy)));
  99.       int id = gid(cur);
  100.       if (id <= m && uline[id] == cur)
  101.         shade[id].push_back(Vec(x1 + x2, y1 + y2) * Vec(cur.A, cur.B));
  102.     }
  103.   for (int i = 1; i <= m; ++i)
  104.     sort(shade[i].begin(), shade[i].end());
  105.   for (int i = 1; i <= n; ++i)
  106.     for (int j = 1; j < i; ++j) {
  107.       Line cur = norm(x[i], y[i], x[j], y[j]);
  108.       int id = gid(cur);
  109.       ll shl = Vec(2LL * x[i], 2LL * y[i]) * Vec(cur.A, cur.B), shr = Vec(2LL * x[j], 2LL * y[j]) * Vec(cur.A, cur.B);
  110.       if (shl > shr)
  111.         swap(shl, shr);
  112.       c1[i][j] = c1[j][i] = upper_bound(shade[id].begin(), shade[id].end(), shr) - lower_bound(shade[id].begin(), shade[id].end(), shl);
  113.     }
  114.   for (int i = 1; i <= n; ++i)
  115.     ve[i] = Vec(x[i], y[i]);
  116.   for (int i = 1; i <= n; ++i) {
  117.     for (int j = 1; j < i; ++j)
  118.       cyc[j] = make_pair(ve[j] - ve[i], j);
  119.     for (int j = i + 1; j <= n; ++j)
  120.       cyc[j - 1] = make_pair(ve[j] - ve[i], j);
  121.     sort(cyc + 1, cyc + n);
  122.   }
  123.   return 0;
  124. }
Advertisement
Add Comment
Please, Sign In to add comment