QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#402448 | #7693. Convex Hull Extension | u2x1 | WA | 1ms | 3780kb | C++20 | 3.6kb | 2024-04-30 16:28:36 | 2024-04-30 16:28:36 |
Judging History
answer
#include "bits/stdc++.h"
#define all(x) x.begin(), x.end()
#define NL std::cout << '\n'
using lnt = long long;
const int inf = 0x3f3f3f3f;
const lnt linf = 1ll << 62;
using db = long double;
const db eps = 1e-15;
int sgn(db x) { return (x < -eps ? -1 : x > eps); }
struct Pt { db x, y; };
Pt readpt() { int x, y; std::cin >> x >> y; Pt p; p.x = x; p.y = y; return p; }
void printpt(Pt p) { std::cout << "(" << p.x << "," << p.y << ")"; }
Pt operator-(Pt a, Pt b) { return { a.x - b.x, a.y - b.y }; }
Pt operator+(Pt a, Pt b) { return { a.x + b.x, a.y + b.y }; }
Pt operator*(Pt a, db x) { return { a.x * x, a.y * x }; }
Pt operator/(Pt a, db x) { return { a.x / x, a.y / x }; }
db dot(Pt a, Pt b) { return a.x * b.x + a.y * b.y; }
db det(Pt a, Pt b) { return a.x * b.y - a.y * b.x; }
bool operator==(Pt a, Pt b) { return !sgn(dot(a-b, a-b)); }
bool operator<(Pt a, Pt b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
db dis2(Pt a, Pt b) { return dot(a-b, a-b); }
db dis(Pt a, Pt b) { return std::sqrt(dis2(a, b)); }
int side(Pt a, Pt b, Pt x) { return sgn(det(b-a, x-a)); }
struct Line { Pt s, t; };
Pt intersect(Line a, Line b) {
db v = det(a.t - a.s, b.s - a.s);
db u = det(a.t - a.s, b.t - a.s);
return (b.s * u - b.t * v) / (u - v);
}
bool para(Line a, Line b) { return !sgn(det(a.t - a.s, b.t - b.s)); }
struct Seg { Pt s, t; };
lnt ptCntOnSeg(Seg p) {
lnt dx = ((p.t - p.s).x), dy = ((p.t - p.s).y);
dx = dx < 0 ? -dx : dx;
dy = dy < 0 ? -dy : dy;
return std::gcd(dx, dy) + 1;
}
int main() {
std::ios::sync_with_stdio(0), std::cin.tie(0);
auto hasInf = []() { std::cout << "infinitely many"; exit(0); };
int n; std::cin >> n;
std::vector<Pt> v(n);
for (int i = 0; i < n; ++i) { v[i] = readpt(); }
lnt ret = 0;
for (int i = 0; i < n; ++i) {
auto l = v[i], r = v[(i+1) % n];
auto l1 = v[i ? i-1 : n-1], r1 = v[(i+2) % n];
if (sgn(det(l - l1, r - r1)) >= 0) {
std::vector<Pt> hull { l, l + (l - l1) * 2500 * 2500, r + (r - r1) * 2500 * 2500, r };
db s = 0; int c = 0;
for (int i = 0; i < hull.size(); ++i) {
s += det(hull[i], hull[(i+1) % hull.size()]);
c += ptCntOnSeg({hull[i], hull[(i+1) % hull.size()]}) - 1;
}
if ((lnt)std::floor(s+eps) / 2 - c / 2 + 1 + (ptCntOnSeg({hull[1], hull[2]}) - 2) > 0) {
hasInf();
}
continue;
}
auto inter = intersect({l1, l}, {r, r1});
lnt kl = std::floor(eps + std::sqrt(dis2(inter, l) / dis2(l, l1)));
lnt kr = std::floor(eps + std::sqrt(dis2(inter, r) / dis2(r, r1)));
std::vector<Pt> tri;
if (kl || kr) {
std::vector<Pt> hull= {l, (l + (l - l1) * kl), (r + (r - r1) * kr), r};
db s = 0; int c = 0;
for (int i = 0; i < hull.size(); ++i) {
s += det(hull[i], hull[(i+1) % hull.size()]);
c += ptCntOnSeg({hull[i], hull[(i+1) % hull.size()]}) - 1;
}
ret += (lnt)std::floor(s+eps) / 2 - c / 2 + 1 + (ptCntOnSeg({hull[1], hull[2]}) - 2);
tri = {hull[1], inter, hull[2]};
} else {
tri = {l, inter, r};
}
db mix = inf, mxx = -inf, miy = inf, mxy = -inf;
for (auto p : tri) {
mix = std::min(mix, p.x); miy = std::min(miy, p.y);
mxx = std::max(mxx, p.x); mxy = std::max(mxy, p.y);
}
for (int x = mix - 1; x <= mxx + 1; ++x) {
for (int y = miy - 1; y <= mxy + 1; ++y) {
Pt p {(db)x, (db)y};
ret += side(tri[0], tri[1], p) > 0 && side(tri[1], tri[2], p) > 0 && side(tri[2], tri[0], p) > 0;
}
}
}
std::cout << ret;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3560kb
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: 3780kb
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: 3552kb
input:
4 -1000 1000 -1000 999 -999 999 -999 1000
output:
0
result:
ok single line: '0'
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3452kb
input:
6 0 -901 900 -900 900 900 0 901 -900 900 -900 -900
output:
1458000000
result:
wrong answer 1st lines differ - expected: '1457999998', found: '1458000000'