QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#250726 | #7693. Convex Hull Extension | funnuf | WA | 1ms | 3640kb | C++17 | 5.2kb | 2023-11-13 16:09:34 | 2023-11-13 16:09:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define rep(i, j, k) for (ll i = j; i <= k; ++i)
#define per(i, j, k) for (ll i = j; i >= k; --i)
#define closeSync \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0)
#define pii pair<ll, ll>
#define fi first
#define se second
const ll INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
#define double long double
#define int long long
const double eps = 1e-8;
struct Point {
double x, y;
Point() {
}
Point(double x, double y) :
x(x), y(y) {
}
bool operator<(const Point &it) {
if (abs(x - it.x) >= eps) return x < it.x;
if (abs(y - it.y) >= eps) return y < it.y;
return 0;
}
};
typedef Point Vector;
Vector operator+(Point A, Point B) {
return Vector(A.x + B.x, A.y + B.y);
}
Vector operator-(Point A, Point B) {
return Vector(A.x - B.x, A.y - B.y);
}
Vector operator*(Vector A, double p) {
return Vector(A.x * p, A.y * p);
}
Vector operator/(Vector A, double p) {
return Vector(A.x / p, A.y / p);
}
double Dot(Vector A, Vector B) {
return A.x * B.x + A.y * B.y;
}
double Length(Vector A) {
return sqrt(Dot(A, A));
}
double Cross(Vector A, Vector B) { // 叉积
return A.x * B.y - A.y * B.x;
}
int dcmp(double x) {
if (abs(x) < eps)
return 0;
else if (x < 0)
return -1;
return 1;
}
double DistanceDotToLine(Point P, Point A, Point B) {
Vector v1 = B - A, v2 = P - A;
return fabs(Cross(v1, v2) / Length(v1));
}
Point GedLineIntersection(Point P, Vector v, Point Q, Vector w) { // 交点
Vector u = P - Q;
double t = Cross(w, u) / Cross(v, w);
return P + v * t;
}
Point P[55];
int n;
int pre(int x) {
if (x == 1) return n;
return x - 1;
}
int aft(int x) {
if (x == n) return 1;
return x + 1;
}
int _ceil(double x) {
int xx = ceil(x);
if (abs(x - (xx - 1)) < eps) return xx - 1;
return xx;
}
int _floor(double x) {
int xx = floor(x);
if (abs(x - (xx + 1)) < eps) return xx + 1;
return xx;
}
int cal(Point A, Point B, Point C) {
int res = 0;
// Point lb = {min({A.x, B.x, C.x}), min({A.y, B.y, C.y})};
// Point rt = {max({A.x, B.x, C.x}), max({A.y, B.y, C.y})};
vector<Point> vec;
vec.push_back(A);
vec.push_back(B);
vec.push_back(C);
sort(vec.begin(), vec.end());
A = vec[0];
B = vec[1];
C = vec[2];
if (abs(B.x - C.x) < eps) {
A.x = 2 * B.x - A.x;
Point tmp = A;
A = B;
B = C;
C = tmp;
}
if (abs(A.x - B.x) < eps) {
Point pb = A, pc = A;
double dy_AC = (C.y - A.y) / (C.x - A.x);
double dy_AB = (B.y - A.y) / (B.x - A.x);
pb.y -= abs(A.x - _floor(A.x)) * dy_AB;
pc.y -= abs(A.x - _floor(A.x)) * dy_AC;
rep(i, _floor(A.x) + 1, _floor(C.x)) {
pb.y += dy_AB;
pc.y += dy_AC;
double tp = max(pb.y, pc.y);
double bt = min(pb.y, pc.y);
res += (_ceil(tp) - 1) - (_floor(bt) + 1) + 1;
}
} else {
// cout << A.x << " " << A.y << " -- A\n";
// cout << B.x << " " << B.y << " -- B\n";
// cout << C.x << " " << C.y << " -- C\n";
Point pb = A, pc = A;
double dy_AC = (C.y - A.y) / (C.x - A.x);
double dy_AB = (B.y - A.y) / (B.x - A.x);
// cout << dy_AC << " " << dy_AB << "\n";
pb.y -= abs(A.x - _floor(A.x)) * dy_AB;
pc.y -= abs(A.x - _floor(A.x)) * dy_AC;
// cout << pb.y << " " << pc.y << "\n";
rep(i, _floor(A.x) + 1, _floor(B.x)) {
// cout << i << "\n";
pb.y += dy_AB;
pc.y += dy_AC;
double tp = max(pb.y, pc.y);
double bt = min(pb.y, pc.y);
res += (_ceil(tp) - 1) - (_floor(bt) + 1) + 1;
// cout << "case1: " << i << " " << bt << " " << tp << " " << (_ceil(tp) - 1) - (_floor(bt) + 1) + 1 << " " << _ceil(tp) << " " << _floor(bt) << "\n";
}
pb = B;
double dy_BC = (C.y - B.y) / (C.x - B.x);
pb.y -= abs(B.y - _floor(B.y)) * dy_BC;
rep(i, _floor(B.x) + 1, _ceil(C.x) - 1) {
// cout << i << "\n";
pc.y += dy_AC;
pb.y += dy_BC;
double tp = max(pb.y, pc.y);
double bt = min(pb.y, pc.y);
res += (_ceil(tp) - 1) - (_floor(bt) + 1) + 1;
// cout << "case2: " << i << " " << bt << " " << tp << " " << (_ceil(tp) - 1) - (_floor(bt) + 1) + 1 << "\n";
}
}
return res;
}
void solve() {
cin >> n;
rep(i, 1, n) {
cin >> P[i].x >> P[i].y;
}
ll ans = 0;
rep(i, 1, n) {
int p1 = pre(i);
int p2 = aft(i);
if (Cross(P[p1] - P[i], P[aft(p2)] - P[p2]) >= 0) {
cout << "infinitely many";
return;
}
Point Q = GedLineIntersection(P[i], P[p1] - P[i], P[p2], P[aft(p2)] - P[p2]);
ans += cal(P[i], P[p2], Q);
}
cout << ans;
}
signed main() {
closeSync;
// int T;cin>>T;while(T--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3640kb
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: 3580kb
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: 1ms
memory: 3572kb
input:
4 -1000 1000 -1000 999 -999 999 -999 1000
output:
infinitely many
result:
wrong answer 1st lines differ - expected: '0', found: 'infinitely many'