QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#402419 | #7693. Convex Hull Extension | u2x1 | WA | 1ms | 3840kb | C++20 | 3.5kb | 2024-04-30 15:38:49 | 2024-04-30 15:38:51 |
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-12;
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)); }
db area(Pt a, Pt b, Pt c) { return std::abs(det(a - b, a - c)); }
int side(Pt a, Pt b, Pt x) { return sgn(det(b-a, x-a)); }
Pt rot90(Pt a) { return {-a.y, a.x}; }
Pt unit(Pt a) {
db d = dis(a, {0, 0});
return sgn(d) ? a/d : Pt{0, 0};
}
struct Line { Pt s, t; };
db pt2line(Pt x, Line l) {
if (l.s == l.t) { return dis(l.s, x); }
return std::abs(det(x - l.s, x - l.t) / dis(l.s, l.t));
}
bool ptonline(Pt x, Line l) {
if (l.s == l.t) { return sgn(dis2(l.s, x)) == 0; }
return sgn(det(l.s - x, l.t - x)) == 0;
}
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 = std::abs((p.t - p.s).x), dy = std::abs((p.t - p.s).y);
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 (para({l1, l}, {r1, r})) { hasInf(); }
auto inter = intersect({l1, l}, {r, r1});
if (side(l, r, inter) == 1) { hasInf(); }
db k = (inter.x - r.x) / (r.x - r1.x);
int fk = std::floor(k + eps);
std::vector<Pt> hull({l, r});
std::vector<Pt> tri;
if (fk != 0) {
hull= {l, (l + (l - l1) * fk), (r + (r - r1) * fk), 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: 3652kb
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: 3552kb
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: 3840kb
input:
4 -1000 1000 -1000 999 -999 999 -999 1000
output:
infinitely many
result:
wrong answer 1st lines differ - expected: '0', found: 'infinitely many'