QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#339526#7693. Convex Hull ExtensionlonelywolfWA 25ms4004kbC++204.8kb2024-02-27 15:14:122024-02-27 15:14:12

Judging History

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

  • [2024-02-27 15:14:12]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:4004kb
  • [2024-02-27 15:14:12]
  • 提交

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 0;
                }
            }   
            if (cmp(a.x, b.x) == 0) {
                if (!calc(a.x, c.x)) {
                    return 0;
                }
            }   
            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;
}

詳細信息

Test #1:

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

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

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

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

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

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

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

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

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

input:

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

output:

4794

result:

ok single line: '4794'

Test #10:

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

input:

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

output:

infinitely many

result:

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