QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#339525#7693. Convex Hull ExtensionlonelywolfWA 25ms3996kbC++204.8kb2024-02-27 15:11:132024-02-27 15:11:13

Judging History

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

  • [2024-02-27 15:11:13]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:3996kb
  • [2024-02-27 15:11:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long
using db = double;

const db eps = 1e-9;
int sgn(db a) {
    if(a > eps) return 1;
    else if(a < -eps) return -1;
    else return 0;
}
// a < b : -1 | a == b : 0 | a > b : 1
int cmp(db a, db b) {
    return sgn(a - b);
}
// x in [a, b]
bool inmid(db x, db a, db b) {
    return sgn(x - a) * sgn(x - b) <= 0;
}

//点
struct point {
    db x, y;
    point operator + (const point &p) const {
        return {x + p.x, y + p.y};
    }
    point operator - (const point &p) const {
        return {x - p.x, y - p.y};
    }
    point operator * (db k) const {
        return {k * x , k * y};
    }
    point operator / (db k) const {
        return {x / k , y / k};
    }
    bool operator == (const point &p) const {
        return cmp(x, p.x) == 0 && cmp(y, p.y) == 0;
    }   
    // 优先比较 x 坐标
    bool operator < (const point &p) const {
        int t = cmp(x, p.x);
        if(t != 0) return t == -1;
        return cmp(y, p.y) == -1;
    }
    // 模长
    db len() {
        return sqrt(x * x + y * y);
    }
    // 模长平方
    db len2() {
        return x * x + y * y;
    }
    // 单位化(模长 > 0)
    point unit() {
        return (*this) / len();
    }
    // 极角 (-pi, pi]
    db getw() {
        return atan2(y, x);
    }
    // 逆时针旋转 k 弧度
    point rot(db k) {
        return {x * cos(k) - y * sin(k), x * sin(k) + y * cos(k)};
    }   
    // 逆时针旋转90°
    point rotleft() {
        return {-y, x};
    }
    // 将向量对称到 (-pi / 2, pi / 2] 半平面上
    point getdel() {
        if(sgn(x) == -1 || (sgn(x) == 0 && sgn(y) == -1)) {
            return (*this) * (-1);
        } else {
            return *this;
        }
    }
    // 判断在 y 轴上侧下侧 ( (-pi, 0] : 0 | (0, pi] : 1 )
    int getP() {
        return sgn(y) == 1 || (sgn(y) == 0 && sgn(x) == -1);
    }
    friend istream &operator >> (istream &is, point &p) {
        return is >> p.x >> p.y;
    }
    friend ostream &operator << (ostream &os, point &p) {
        return os << p.x << " " << p.y;
    }
    
};
db cross(point a, point b) {
    return a.x * b.y - a.y * b.x;
}
bool inmid(point p, point a, point b) {
    return inmid(p.x, a.x, b.x) && inmid(p.y, a.y, b.y);
}
point getLL(point a, point b, point c, point d) {
    db w1 = cross(a - c, d - c), w2 = cross(d - c, b - c);
    return (a * w2 + b * w1) / (w1 + w2);
}
int calc(db l, db r) {
    if (cmp(l, r) == 1) {
        swap(l, r);
    }
    int L = ceil(l), R = floor(r);
    if (cmp(L, l) == 0) {
        L++;
    }
    if (cmp(R, r) == 0) {
        R--;
    }
    return max(0ll, R - L + 1);
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<point> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    auto check = [&] (point a, point b, point c, point d) -> bool {
        if (sgn(cross(a - b, c - d)) == 1) {
            return 1;
        }
        if (sgn(cross(a - b, c - d)) == 0) {
            if (cmp(a.y, b.y) == 0) {
                if (calc(a.y, c.y)) {
                    return 1;
                }
            }   
            if (cmp(a.x, b.x) == 0) {
                if (calc(a.x, c.x)) {
                    return 1;
                }
            }   
        }
        return 0;
    };
    auto work = [&] (array<point, 3> S, int a) {
        db l = 1e100, r = -1e100;
        for (int i = 0; i < 3; i++) {
            point p1 = S[i], p2 = S[(i + 1) % 3];
            point c = getLL(p1, p2, {a, 0}, {a, 1});
            if (inmid(c, p1, p2)) {
                l = min(l, c.y);
                r = max(r, c.y);
            }
        }
        return calc(l, r);
    };
    int ans = 0;
    for (int i = 0; i < n; i++) {
        point p1 = A[i], p2 = A[(i + n - 1) % n], q1 = A[(i + 1) % n], q2 = A[(i + 2) % n];
        if (check(p1, p2, q1, q2)) {
            cout << "infinitely many\n";
            return 0;
        }
        if (sgn(cross(p2 - p1, q2 - q1)) != 0) {
            point m = getLL(p1, p2, q1, q2);
            array<point, 3> s{p1, m, q1};
            db l = 1e100, r = -1e100;
            for (auto p : s) {
                l = min(l, p.x);
                r = max(r, p.x);
            }
            if (cmp(l, r) == 1) {
                swap(l, r);
            }
            int L = ceil(l), R = floor(r);
            if (cmp(L, l) == 0) {
                L++;
            }
            if (cmp(R, r) == 0) {
                R--;
            }
            for (int X = L; X <= R; X++) {
                ans += work(s, X);
            }
        }   
    }
    cout << ans << "\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3704kb

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: 3704kb

input:

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

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 25ms
memory: 3772kb

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: 3992kb

input:

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

output:

1457999998

result:

ok single line: '1457999998'

Test #6:

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

input:

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

output:

1596

result:

ok single line: '1596'

Test #7:

score: 0
Accepted
time: 17ms
memory: 3776kb

input:

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

output:

970921796

result:

ok single line: '970921796'

Test #8:

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

input:

6
2 -2
401 399
399 401
-2 2
-401 -399
-399 -401

output:

4794

result:

ok single line: '4794'

Test #9:

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

input:

6
399 -401
401 -399
2 2
-399 401
-401 399
-2 -2

output:

4794

result:

ok single line: '4794'

Test #10:

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

input:

4
-1 -1
-2 -2
-2 -3
-1 -2

output:

0

result:

ok single line: '0'

Test #11:

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

input:

4
0 0
0 1
-1 2
-1 1

output:

0

result:

ok single line: '0'

Test #12:

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

input:

48
5 -70
14 -68
22 -66
31 -63
39 -58
46 -52
52 -46
58 -39
63 -31
66 -22
68 -14
70 -5
70 5
68 14
66 22
63 31
58 39
52 46
46 52
39 58
31 63
22 66
14 68
5 70
-5 70
-14 68
-22 66
-31 63
-39 58
-46 52
-52 46
-58 39
-63 31
-66 22
-68 14
-70 5
-70 -5
-68 -14
-66 -22
-63 -31
-58 -39
-52 -46
-46 -52
-39 -58
...

output:

36

result:

ok single line: '36'

Test #13:

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

input:

4
-10 -10
-11 11
-11 10
-10 -11

output:

0

result:

ok single line: '0'

Test #14:

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

input:

4
10 -10
10 -11
11 10
11 11

output:

0

result:

ok single line: '0'

Test #15:

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

input:

4
5 5
6 5
-5 6
-6 6

output:

0

result:

ok single line: '0'

Test #16:

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

input:

4
100 -99
-99 -98
-100 -98
99 -99

output:

0

result:

ok single line: '0'

Test #17:

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

input:

4
0 1
-1 0
0 -1
1 0

output:

0

result:

wrong answer 1st lines differ - expected: 'infinitely many', found: '0'