QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#238714#7693. Convex Hull Extensionwillow#WA 0ms3876kbC++143.4kb2023-11-04 17:20:022023-11-04 17:20:04

Judging History

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

  • [2023-11-04 17:20:04]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3876kb
  • [2023-11-04 17:20:02]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double LD;
const int N = 55;
const LD eps = 1e-9;

inline int sgn(LD x) {
    return x > eps? 1 : x < -eps? -1 : 0;
}

int n;
LL X[N], Y[N];

struct Point {
    LD x, y;
    Point(LD _x = 0, LD _y = 0): x(_x), y(_y) {}
    Point operator + (const Point &rhs) const{
        return Point(x + rhs.x, y + rhs.y);
    }
    Point operator - (const Point &rhs) const{
        return Point(x - rhs.x, y - rhs.y);
    }
    Point operator * (const LD &rhs) const{
        return Point(x * rhs, y * rhs);
    }
    Point operator / (const LD &rhs) const{
        return Point(x / rhs, y / rhs);
    }
    LD operator * (const Point &rhs) const{
        return x * rhs.x + y * rhs.y;
    }
    LD operator ^ (const Point &rhs) const {
        return x * rhs.y - y * rhs.x;
    }
} p[N];

Point Intersect(Point u1, Point v1, Point u2, Point v2) {
    LD a1 = (v2 - u2) ^ (u1 - u2), a2 = (v2 - u2) ^ (v1 - u2);
    return (u1 * a2 - v1 * a1) / (a2 - a1);
}

LL SuperEuclid(LL a, LL b, LL c, LL n) {
    if (!a) return (n + 1) * (b / c);
    if (a >= c || b >= c) {
        return (a / c) * (n * (n + 1) / 2) + (b / c) * (n + 1)
                + SuperEuclid(a % c, b % c, c, n);
    }
    LL m = (a * n + b) / c;
    return n * m - SuperEuclid(c, c - b - 1, a, m - 1);
}

LL Calc(LL dx, LL dy, LD dn, LD dm) {
    if (dx < 0) dx = -dx;
    if (dy < 0) dy = -dy;
    LL n = floor(dn), m = floor(dm);
    if (dx == 0) return m + 1;
    if (dy == 0) return n + 1;
    return SuperEuclid(dy, 0, dx, n) + n + 1;
}

void solve() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%Lf %Lf", &p[i].x, &p[i].y);
    }
    p[0] = p[n];
    p[n + 1] = p[1];
    p[n + 2] = p[2];
    for (int i = 0; i <= n + 2; ++i) {
        X[i] = (LL)p[i].x;
        Y[i] = (LL)p[i].y;
    }
    LL ans = 0;
    for (int i = 1; i <= n; ++i) {
        LD tmp = ((p[i] - p[i - 1]) ^ (p[i + 1] - p[i + 2]));
        if (sgn(tmp) >= 0) {
            if (sgn(tmp) == 0 && llabs(X[i] - X[i + 1]) + llabs(Y[i] - Y[i + 1]) == 1) {
                continue;
            }
            puts("infinitely many");
            return;
        }
        Point it = Intersect(p[i - 1], p[i], p[i + 2], p[i + 1]);
        LL w = max(floor(fabs(p[i].x - p[i + 1].x)), max(floor(fabs(p[i].x - it.x)), floor(fabs(p[i + 1].x - it.x))));
        LL h = max(floor(fabs(p[i].y - p[i + 1].y)), max(floor(fabs(p[i].y - it.y)), floor(fabs(p[i + 1].y - it.y))));
        ans += (w + 1) * (h + 1);
        ans -= Calc(X[i + 1] - X[i], Y[i + 1] - Y[i], fabs(p[i + 1].x - p[i].x), fabs(p[i + 1].y - p[i].y));
        if ((X[i + 1] > X[i]) != (Y[i + 1] > Y[i])) {
            ans -= Calc(X[i] - X[i - 1], Y[i] - Y[i - 1], fabs(it.x - p[i].x), fabs(it.y - p[i].y));
            ans -= Calc(Y[i + 1] - Y[i + 2], X[i + 1] - X[i + 2], fabs(it.y - p[i + 1].y), fabs(it.x - p[i + 1].x));
        } else {
            ans -= Calc(Y[i] - Y[i - 1], X[i] - X[i - 1], fabs(it.y - p[i].y), fabs(it.x - p[i].x));
            ans -= Calc(X[i + 1] - X[i + 2], Y[i + 1] - Y[i + 2], fabs(it.x - p[i + 1].x), fabs(it.y - p[i + 1].y));
        }
        ans += 2 + (sgn(it.x - floor(it.x + .5)) == 0 && sgn(it.y - floor(it.y + .5)) == 0);
    }
    printf("%lld\n", ans);
}

int main() {
    solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3820kb

input:

5
0 2
-2 0
-1 -3
1 -3
2 1

output:

23

result:

ok single line: '23'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3736kb

input:

4
-7 -7
7 -7
7 7
-7 7

output:

infinitely many

result:

ok single line: 'infinitely many'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

4
-1000 1000
-1000 999
-999 999
-999 1000

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

6
0 -901
900 -900
900 900
0 901
-900 900
-900 -900

output:

1457999998

result:

ok single line: '1457999998'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

6
900 -900
901 0
900 900
-900 900
-901 0
-900 -900

output:

1457999998

result:

ok single line: '1457999998'

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 3876kb

input:

6
0 0
400 1
400 2
0 3
-400 2
-400 1

output:

1996

result:

wrong answer 1st lines differ - expected: '1596', found: '1996'