QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#339496 | #7693. Convex Hull Extension | lonelywolf | WA | 0ms | 3956kb | C++20 | 4.9kb | 2024-02-27 14:11:15 | 2024-02-27 14:11:16 |
Judging History
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.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;
}
}
}
if (cmp(p1.y, p2.y) == 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;
}
}
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3864kb
input:
5 0 2 -2 0 -1 -3 1 -3 2 1
output:
23
result:
ok single line: '23'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3956kb
input:
4 -7 -7 7 -7 7 7 -7 7
output:
0
result:
wrong answer 1st lines differ - expected: 'infinitely many', found: '0'