QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#339498#7693. Convex Hull ExtensionlonelywolfWA 61ms3752kbC++204.9kb2024-02-27 14:14:072024-02-27 14:14:07

Judging History

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

  • [2024-02-27 14:14:07]
  • 评测
  • 测评结果:WA
  • 用时:61ms
  • 内存:3752kb
  • [2024-02-27 14:14:07]
  • 提交

answer

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

#define int long long
using db = long double;

const db eps = 1e-9;

int sgn(db a) {
    if(a > eps) return 1;
    else if(a < -eps) return -1;
    else return 0;
}
int cmp(db a, db b) {
    return sgn(a - b);
}
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;
    }
    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;
}
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);
}
bool inmid(db x, db a, db b) {
    return sgn(x - a) * sgn(x - b) <= 0;
}
vector<point> ConvexHull(vector<point> A, int flag = 1) {
    int n = A.size();
    if(n == 1) return A;
    if(n == 2) {
        if(A[0] == A[1]) return {A[0]};
        else return A;
    }
    vector<point> ans(2 * n);
    sort(A.begin(), A.end());
    int now = -1;
    for(int i = 0; i < A.size(); i++) {
        while(now > 0 && sgn(cross(ans[now] - ans[now - 1], A[i] - ans[now - 1])) < flag) now--;
        ans[++now] = A[i];
    }
    int pre = now;
    for(int i = n - 2; i >= 0; i--) {
        while(now > pre && sgn(cross(ans[now] - ans[now - 1], A[i] - ans[now - 1])) < flag) now--;
        ans[++now] = A[i];
    }
    ans.resize(now);
    return ans;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int n;
    cin >> n;
    vector<point> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    A = ConvexHull(A);
    n = A.size();
    auto work = [&] (vector<point> m) {
        db l = 1e100, r = -1e100;
        for (auto p : m) {
            l = min(l, p.x);
            r = max(r, p.x);
        }
        int ret = 0;
        for (int X = l - 1; X <= r + 1; X++) {
            db u = -1e100, d = 1e100;
            bool ok = 0;
            for (int i = 0; i < m.size(); i++) {
                point p1 = m[i], p2 = m[(i + 1) % m.size()];
                if (inmid(X, p1.x, p2.x)) {
                    ok = 1;
                    if (cmp(p1.x, p2.x) == 0) {
                        continue;
                    }
                    point c = getLL(p1, p2, {X, 0}, {X, 1});
                    u = max(u, c.y);
                    d = min(d, c.y);
                } 
            }
            if (!ok) {
                continue;
            }
            ret += (floor(u) - ceil(d) + 1); 
            if (cmp(u, floor(u)) == 0) {
                ret--;
            }
            if (cmp(d, ceil(d)) == 0) {
                ret--;
            }
            if (cmp(u, d) == 0 && cmp(d, ceil(d)) == 0 && cmp(u, floor(u)) == 0) {
                ret++;
            }
            // cerr << "(" << u << " " << floor(u) << ")";
            // cerr << "(" << d << " " << ceil(d) << ")";
            // cerr << X << " " << ret << "\n";
        }
        return ret;
    };
    int ans = 0;
    for (int i = 0; i < n; i++) {
        point p1 = A[i], p2 = A[(i + 1) % n], p3 = A[(i + 3) % n], p4 = A[(i + 2) % n];
        if (sgn(cross(p2 - p1, p4 - p3)) > 0) {
            cout << "infinitely many\n";
            return 0;
        }
        if (sgn(cross(p2 - p1, p4 - p3)) == 0) {
            if (cmp(p1.x, p2.x) == 0) {
                db l = min(p1.x, p3.x), r = max(p1.x, p3.x);
                int a = l;
                for (int i = a; i <= a + 5; i++) {
                    if (cmp(l, i) < 0 && cmp(i, r) < 0) {
                        cout << "infinitely many\n";
                        return 0;   
                    }
                }
            }
            if (cmp(p1.y, p2.y) == 0) {
                db l = min(p1.y, p3.y), r = max(p1.y, p3.y);
                int a = l;
                for (int i = a; i <= a + 5; i++) {
                    if (cmp(l, i) < 0 && cmp(i, r) < 0) {
                        cout << "infinitely many\n";
                        return 0;   
                    }
                }
            }
            continue;
        }
        vector<point> t;
        t.push_back(p4), t.push_back(p2), t.push_back(getLL(p1, p2, p3, p4));
        ans += work(t);
    }
    cout << ans << "\n";
	return 0;
}

详细

Test #1:

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

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

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

input:

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

output:

0

result:

ok single line: '0'

Test #4:

score: -100
Wrong Answer
time: 61ms
memory: 3748kb

input:

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

output:

1458003600

result:

wrong answer 1st lines differ - expected: '1457999998', found: '1458003600'