QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#238624 | #7693. Convex Hull Extension | willow# | WA | 0ms | 3828kb | C++14 | 3.2kb | 2023-11-04 17:09:22 | 2023-11-04 17:09:23 |
Judging History
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) {
if (((p[i] - p[i - 1]) ^ (p[i + 1] - p[i + 2])) >= 0) {
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3808kb
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: 3828kb
input:
4 -7 -7 7 -7 7 7 -7 7
output:
infinitely many
result:
ok single line: 'infinitely many'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3816kb
input:
4 -1000 1000 -1000 999 -999 999 -999 1000
output:
infinitely many
result:
wrong answer 1st lines differ - expected: '0', found: 'infinitely many'