QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#339525 | #7693. Convex Hull Extension | lonelywolf | WA | 25ms | 3996kb | C++20 | 4.8kb | 2024-02-27 15:11:13 | 2024-02-27 15:11:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
using db = double;
const db eps = 1e-9;
int sgn(db a) {
if(a > eps) return 1;
else if(a < -eps) return -1;
else return 0;
}
// a < b : -1 | a == b : 0 | a > b : 1
int cmp(db a, db b) {
return sgn(a - b);
}
// x in [a, b]
bool inmid(db x, db a, db b) {
return sgn(x - a) * sgn(x - b) <= 0;
}
//点
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;
}
// 模长
db len() {
return sqrt(x * x + y * y);
}
// 模长平方
db len2() {
return x * x + y * y;
}
// 单位化(模长 > 0)
point unit() {
return (*this) / len();
}
// 极角 (-pi, pi]
db getw() {
return atan2(y, x);
}
// 逆时针旋转 k 弧度
point rot(db k) {
return {x * cos(k) - y * sin(k), x * sin(k) + y * cos(k)};
}
// 逆时针旋转90°
point rotleft() {
return {-y, x};
}
// 将向量对称到 (-pi / 2, pi / 2] 半平面上
point getdel() {
if(sgn(x) == -1 || (sgn(x) == 0 && sgn(y) == -1)) {
return (*this) * (-1);
} else {
return *this;
}
}
// 判断在 y 轴上侧下侧 ( (-pi, 0] : 0 | (0, pi] : 1 )
int getP() {
return sgn(y) == 1 || (sgn(y) == 0 && sgn(x) == -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;
}
bool inmid(point p, point a, point b) {
return inmid(p.x, a.x, b.x) && inmid(p.y, a.y, b.y);
}
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);
}
int calc(db l, db r) {
if (cmp(l, r) == 1) {
swap(l, r);
}
int L = ceil(l), R = floor(r);
if (cmp(L, l) == 0) {
L++;
}
if (cmp(R, r) == 0) {
R--;
}
return max(0ll, R - L + 1);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<point> A(n);
for (int i = 0; i < n; i++) {
cin >> A[i];
}
auto check = [&] (point a, point b, point c, point d) -> bool {
if (sgn(cross(a - b, c - d)) == 1) {
return 1;
}
if (sgn(cross(a - b, c - d)) == 0) {
if (cmp(a.y, b.y) == 0) {
if (calc(a.y, c.y)) {
return 1;
}
}
if (cmp(a.x, b.x) == 0) {
if (calc(a.x, c.x)) {
return 1;
}
}
}
return 0;
};
auto work = [&] (array<point, 3> S, int a) {
db l = 1e100, r = -1e100;
for (int i = 0; i < 3; i++) {
point p1 = S[i], p2 = S[(i + 1) % 3];
point c = getLL(p1, p2, {a, 0}, {a, 1});
if (inmid(c, p1, p2)) {
l = min(l, c.y);
r = max(r, c.y);
}
}
return calc(l, r);
};
int ans = 0;
for (int i = 0; i < n; i++) {
point p1 = A[i], p2 = A[(i + n - 1) % n], q1 = A[(i + 1) % n], q2 = A[(i + 2) % n];
if (check(p1, p2, q1, q2)) {
cout << "infinitely many\n";
return 0;
}
if (sgn(cross(p2 - p1, q2 - q1)) != 0) {
point m = getLL(p1, p2, q1, q2);
array<point, 3> s{p1, m, q1};
db l = 1e100, r = -1e100;
for (auto p : s) {
l = min(l, p.x);
r = max(r, p.x);
}
if (cmp(l, r) == 1) {
swap(l, r);
}
int L = ceil(l), R = floor(r);
if (cmp(L, l) == 0) {
L++;
}
if (cmp(R, r) == 0) {
R--;
}
for (int X = L; X <= R; X++) {
ans += work(s, X);
}
}
}
cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3996kb
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: 3704kb
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: 3704kb
input:
4 -1000 1000 -1000 999 -999 999 -999 1000
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 25ms
memory: 3772kb
input:
6 0 -901 900 -900 900 900 0 901 -900 900 -900 -900
output:
1457999998
result:
ok single line: '1457999998'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3992kb
input:
6 900 -900 901 0 900 900 -900 900 -901 0 -900 -900
output:
1457999998
result:
ok single line: '1457999998'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
6 0 0 400 1 400 2 0 3 -400 2 -400 1
output:
1596
result:
ok single line: '1596'
Test #7:
score: 0
Accepted
time: 17ms
memory: 3776kb
input:
6 0 -901 900 -899 900 900 0 901 -900 900 -900 -899
output:
970921796
result:
ok single line: '970921796'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
6 2 -2 401 399 399 401 -2 2 -401 -399 -399 -401
output:
4794
result:
ok single line: '4794'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
6 399 -401 401 -399 2 2 -399 401 -401 399 -2 -2
output:
4794
result:
ok single line: '4794'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
4 -1 -1 -2 -2 -2 -3 -1 -2
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
4 0 0 0 1 -1 2 -1 1
output:
0
result:
ok single line: '0'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
48 5 -70 14 -68 22 -66 31 -63 39 -58 46 -52 52 -46 58 -39 63 -31 66 -22 68 -14 70 -5 70 5 68 14 66 22 63 31 58 39 52 46 46 52 39 58 31 63 22 66 14 68 5 70 -5 70 -14 68 -22 66 -31 63 -39 58 -46 52 -52 46 -58 39 -63 31 -66 22 -68 14 -70 5 -70 -5 -68 -14 -66 -22 -63 -31 -58 -39 -52 -46 -46 -52 -39 -58 ...
output:
36
result:
ok single line: '36'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
4 -10 -10 -11 11 -11 10 -10 -11
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
4 10 -10 10 -11 11 10 11 11
output:
0
result:
ok single line: '0'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
4 5 5 6 5 -5 6 -6 6
output:
0
result:
ok single line: '0'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
4 100 -99 -99 -98 -100 -98 99 -99
output:
0
result:
ok single line: '0'
Test #17:
score: -100
Wrong Answer
time: 0ms
memory: 3844kb
input:
4 0 1 -1 0 0 -1 1 0
output:
0
result:
wrong answer 1st lines differ - expected: 'infinitely many', found: '0'