Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #include <numeric>
- #include <vector>
- #define LOG(FMT...) fprintf(stderr, FMT)
- using namespace std;
- typedef long long ll;
- typedef pair<ll, pair<ll, ll> > Line;
- struct Vec {
- ll x, y;
- Vec(ll x = 0, ll y = 0) : x(x), y(y) {}
- Vec operator+(const Vec& rhs) const { return Vec(x + rhs.x, y + rhs.y); }
- Vec operator-() const { return Vec(-x, -y); }
- Vec operator-(const Vec& rhs) const { return *this - rhs; }
- ll operator^(const Vec& rhs) const { return x * rhs.x + y * rhs.y; }
- ll operator*(const Vec& rhs) const { return x * rhs.y - y * rhs.x; }
- bool operator<(const Vec& rhs) const;
- bool operator==(const Vec& rhs) const { return *this * rhs == 0; }
- };
- const int N = 1010;
- int n, m;
- int x[N], y[N];
- int c1[N][N], c2[N][N];
- Line uline[N * N];
- pair<Vec, int> cyc[N];
- Vec ve[N], pl[N * 3];
- vector<ll> shade[N * N];
- #define C first
- #define A second.first
- #define B second.second
- ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
- Line norm(const Line& line) {
- ll a = line.A, b = line.B, c = line.C;
- ll g = gcd(gcd(a, b), c);
- a /= g;
- b /= g;
- c /= g;
- if (c < 0) {
- a = -a;
- b = -b;
- c = -c;
- }
- return make_pair(c, make_pair(a, b));
- }
- Line norm(int x1, int y1, int x2, int y2) {
- int dx = x2 - x1, dy = y2 - y1;
- ll a = dy, b = -dx, c = dx * (ll)y1 - dy * (ll)x1;
- return norm(make_pair(c, make_pair(a, b)));
- }
- int gid(const Line& line) { return lower_bound(uline + 1, uline + m + 1, line) - uline; }
- int gr(const Vec& v) {
- LOG("REG %lld %lld\n", v.x, v.y);
- if (v.y == 0)
- return v.x < 0;
- return y < 0;
- }
- bool Vec::operator<(const Vec& rhs) const {
- int r1 = gr(*this), r2 = gr(rhs);
- if (r1 != r2)
- return r1 < r2;
- return *this * rhs > 0;
- }
- int main() {
- scanf("%d", &n);
- for (int i = 1; i <= n; ++i)
- scanf("%d%d", &x[i], &y[i]);
- for (int i = 1; i <= n; ++i)
- for (int j = 1; j < i; ++j)
- uline[++m] = norm(x[i], y[i], x[j], y[j]);
- sort(uline + 1, uline + m + 1);
- m = unique(uline + 1, uline + m + 1) - uline - 1;
- for (int i = 1; i <= n; ++i)
- for (int j = 1; j < i; ++j) {
- // k = -dx/dy
- // 2dyy-dy(y1+y2)=-2dxx+dx(x1+x2)
- // 2dxx+2dyy-dy(y1+y2)-dx(x1+x2)
- int x1 = x[i], y1 = y[i], x2 = x[j], y2 = y[j];
- int dy = y2 - y1, dx = x2 - x1;
- Line cur = norm(make_pair(-dy * (ll)(y1 + y2) - dx * (ll)(x1 + x2), make_pair(2LL * dx, 2LL * dy)));
- int id = gid(cur);
- if (id <= m && uline[id] == cur)
- shade[id].push_back(Vec(x1 + x2, y1 + y2) * Vec(cur.A, cur.B));
- }
- for (int i = 1; i <= m; ++i)
- sort(shade[i].begin(), shade[i].end());
- for (int i = 1; i <= n; ++i)
- for (int j = 1; j < i; ++j) {
- Line cur = norm(x[i], y[i], x[j], y[j]);
- int id = gid(cur);
- 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);
- if (shl > shr)
- swap(shl, shr);
- c1[i][j] = c1[j][i] = upper_bound(shade[id].begin(), shade[id].end(), shr) - lower_bound(shade[id].begin(), shade[id].end(), shl);
- }
- for (int i = 1; i <= n; ++i)
- ve[i] = Vec(x[i], y[i]);
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j < i; ++j)
- cyc[j] = make_pair(ve[j] - ve[i], j);
- for (int j = i + 1; j <= n; ++j)
- cyc[j - 1] = make_pair(ve[j] - ve[i], j);
- sort(cyc + 1, cyc + n);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment