QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#560247#8669. 正方形计数ORzyzRO0 1875ms3676kbC++147.6kb2024-09-12 14:34:142024-09-12 14:34:14

Judging History

你现在查看的是最新测评结果

  • [2024-09-12 14:34:14]
  • 评测
  • 测评结果:0
  • 用时:1875ms
  • 内存:3676kb
  • [2024-09-12 14:34:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pr pair<int, int>
#define pb push_back
#define mid (l + r) / 2
#define ls num << 1
#define rs num << 1 | 1

inline int read() {
    int x = 0, m = 1;
    char ch = getchar();

    while (!isdigit(ch)) {
        if (ch == '-') m = -1;
        ch = getchar();
    }

    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }

    return x * m;
}

inline void write(int x) {
    if (x < 0) {
        putchar('-');
        write(-x);
        return;
    }

    if (x >= 10) write(x / 10);
    putchar(x % 10 + '0');
}

#define double long double

const double eps = 1e-10, Pi = acos(-1), inf = 1e6;

const int N = 20;

struct dot {
    double x, y;
    dot(double x = 0, double y = 0) : x(x), y(y) {}
} a[N];

struct Vec {
    double x, y;
    Vec(double x = 0, double y = 0) : x(x), y(y) {}
};

struct line {
    dot x, y;
    pr k, b;
    line(dot x = dot(), dot y = dot(), pr k = {0, 0}, pr b = {0, 0}) : x(x), y(y), k(k), b(b) {}

    double angle() {
        return atan2(y.y - x.y, y.x - x.x);
    }
} b[N], c[N], h[N], A[4];

line rev(line x) {
    return line(x.y, x.x, x.k, x.b);
}

Vec operator - (dot x, dot y) {
    return Vec(y.x - x.x, y.y - x.y);
}

dot operator + (dot x, Vec y) {
    return dot(x.x + y.x, x.y + y.y);
}

line operator + (line x, Vec y) {
    pr now = x.b;
    now.first += y.y * now.second;
    now.first -= x.k.first * y.x;
    return line(x.x + y, x.y + y, x.k, now);
}

int dcmp(double x) {
    if (fabs(x) < eps) return 0;
    return (x > 0) ? 1 : -1;
}

double operator * (Vec x, Vec y) {
    return x.x * y.y - x.y * y.x;
}

double operator == (dot x, dot y) {
    return dcmp(x.x - y.x) == 0 && dcmp(x.y - y.y) == 0;
}

bool check(Vec x, Vec y) {
    return dcmp(x * y) < 0;
}

bool check(line x, dot y) {
    return check(x.y - x.x, y - x.x);
}

dot cross(line x, line y) {
    Vec x1 = y.y - x.x, x2 = x.y - x.x, x3 = y.x - x.x;
    double S1 = x1 * x2, S2 = x3 * x2;
    return dot((S1 * y.x.x - S2 * y.y.x) / (S1 - S2), (S1 * y.x.y - S2 * y.y.y) / (S1 - S2));
}

bool operator < (line x, line y) {
    double xt = x.angle();
    double yt = y.angle();
    if (dcmp(xt - yt) != 0) return xt < yt;
    if (x.x == y.x) return check(x, y.y);
    return check(x, y.x);
}

int f(int n, int a, int b, int c) {
    if (n < 0) return 0;
    if (!n) return (b / c);
    if (!a) return (n + 1) * (b / c);
    if (a >= c || b >= c) return (n + 1) * (b / c) + n * (n + 1) / 2 * (a / c) + f(n, a % c, b % c, c);
    int M = (a * n + b) / c;
    return n * M - f(M - 1, c, c - b - 1, a);
}

int calc(int l, int r, int a, int b, int c) {
    b += c;
    // cout << " Query " << l << ' ' << r << ' ' << a << ' ' << b << ' ' << c << ' ';
    if (l > r) return 0;
    if (a == 0) {
        if (b < 0) return 0;
        return (r - l + 1) * (b / c);
    }
    if (a < 0) {
        b = a * r + b;
        r = r - l;
        l = 0;
        a = -a;
    }
    // cout << "[" << l << ' ' << r << ' ' << a << ' ' << b << ' ' << c << "] ";
    if (b < 0) {
        l = max(l, (-b + a - 1) / a);
        if (l > r) return 0;
        b = a * l - b;
        r = r - l;
        l = 0;
    }
    return f(r, a, b, c) - f(l - 1, a, b, c);
}

int calc(int n) {
    double minn = 2000, maxn = 0;
    for (int i = 1; i <= n; i++) {
        minn = min(minn, a[i].x);
        maxn = max(maxn, a[i].x);
    }
    if (minn == maxn) {
        if (dcmp(ceil(minn) - minn) != 0) return 0;
        minn = 2000;
        maxn = 0;
        for (int i = 1; i <= n; i++) {
            minn = min(minn, a[i].y);
            maxn = max(maxn, a[i].y);
        }
        return floor(maxn) - ceil(minn) + 1;
    }
    int ans = 0;
    dot A(minn, -2000);
    for (int i = 1; i <= n; i++) {
        int x = i % n + 1;
        if (dcmp(a[i].x - a[x].x) == 0) continue;
        double l = min(a[i].x, a[x].x), r = max(a[i].x, a[x].x);
        int L = ceil(l), R = floor(r);
        if (dcmp(l - minn) != 0 && dcmp(L - l) == 0) L++;
        int a = h[i].k.first, b = h[i].b.first, c = h[i].k.second;
        assert(h[i].k.second == h[i].b.second && h[i].k.second != 0);
        if (check(h[i], A)) {
            b--;
            // cout << " Dec";
            int res = calc(L, R, a, b, c);
            ans -= res;
            // cout << res << '\n';
        }
        else {
            // cout << " Add";
            int res = calc(L, R, a, b, c);
            ans += res;
            // cout << res << '\n';
        }
    }
    return ans;
}

signed main() {
    int n = read(), maxx = 0, minx = 2000, maxy = 0, miny = 2000;

    for (int i = 1; i <= n; i++) {
        a[i].x = read();
        a[i].y = read();
        maxx = max(maxx, (int)a[i].x);
        minx = min(minx, (int)a[i].x);
        maxy = max(maxy, (int)a[i].y);
        miny = min(miny, (int)a[i].y);
    }

    reverse(a + 1, a + n + 1);

    for (int i = 1; i <= n; i++) {
        int x = i % n + 1;
        int X = a[x].x - a[i].x, Y = a[x].y - a[i].y;
        int k = __gcd(X, Y);
        X /= k;
        Y /= k;
        if (X < 0) X = -X, Y = -Y;
        int Z = a[i].y * X - a[i].x * Y;
        b[i] = line(a[i], a[x], {Y, X}, {Z, X});
    }
    sort(b + 1, b + n + 1);

    int limx = maxx - minx, limy = maxy - miny;

    int V = max(limx, limy), ans = 0;

    for (int x = 0; x <= limx; x++) {
        for (int y = x; x + y <= V && y <= limy; y++) {
            if (!y) continue;
            Vec x1(-x, y);
            Vec x2(-y, -x);
            Vec x3(-x - y, y - x);
            for (int i = 1; i <= n; i++) {
                A[0] = b[i];
                A[1] = b[i] + x1;
                A[2] = b[i] + x2;
                A[3] = b[i] + x3;
                sort(A, A + 4);
                c[i] = A[0];
            }
            int l = 1, r = 0, P = 1;
            for (int i = 1; i <= n; i++) {
                while (l < r && check(c[i], a[r])) r--;
                while (l < r && check(c[i], a[l + 1])) l++;
                h[++r] = c[i];
                // for (int j = l; j <= r; j++) {
                //     printf("(%.3Lf, %.3Lf) (%.3Lf, %.3Lf)\n", h[j].x.x, h[j].x.y, h[j].y.x, h[j].y.y);
                // }
                // putchar('\n');
                if (l < r) {
                    if (dcmp(fabs(h[r - 1].angle() - h[r].angle()) - Pi) == 0 && check(h[r], h[r - 1].x)) {
                        P = 0;
                        break;
                    }
                    a[r] = cross(h[r - 1], h[r]);
                }
            }
            if (P) {
                while (l < r && check(h[l], a[r])) r--;
                a[l] = cross(h[l], h[r]);
                P = 1;
                for (int i = 1; i <= n; i++) {
                    if (check(c[i], a[l])) {
                        P = 0;
                        break;
                    }
                }
                if (P) {
                    for (int i = 1; i <= r - l + 1; i++) a[i] = a[i + l - 1], h[i] = h[i + l - 1];
                    if (l + 1 < r) {
                        // for (int i = 1; i <= r - l + 1; i++) {
                        //     printf("(%.3Lf, %.3Lf) (%.3Lf %.3Lf) (%.3Lf %.3Lf)\n", a[i].x, a[i].y, h[i].x.x, h[i].x.y, h[i].y.x, h[i].y.y);
                        // }
                        int res = calc(r - l + 1);
                        // cout << ' ' << x << ' ' << y << ' ' << res << '\n';
                        ans += res;
                    }
                }
            }
        }
    }

    write(ans);
    putchar('\n');
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1875ms
memory: 3652kb

input:

4
131 603
131 1828
1919 1828
1919 603

output:

181368388464

result:

wrong answer 1st numbers differ - expected: '361182910200', found: '181368388464'

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 1725ms
memory: 3676kb

input:

3
131 603
131 1828
1919 603

output:

30566051316

result:

wrong answer 1st numbers differ - expected: '63739309181', found: '30566051316'

Subtask #3:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 1ms
memory: 3520kb

input:

8
0 13
4 15
15 15
15 6
13 1
12 0
5 0
0 6

output:

1143

result:

wrong answer 1st numbers differ - expected: '4047', found: '1143'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%