QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#262742 | #876. Big Brother | Fyind | WA | 1ms | 3764kb | C++23 | 4.3kb | 2023-11-23 22:43:39 | 2023-11-23 22:43:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> pii;
const int maxn = 1e4 + 5;
int n, m;
#define _ << " "<<
#define sz(x) ((int)x.size())
typedef long double ld;
const ld eps = 1e-17;
struct Point {
ld x,y;
Point(ld x=0,ld y = 0) : x(x), y(y) {}
};
ld dcmp(ld x) {
if (fabs(x) < eps) return 0; else return x < 0 ? -1 : 1;
}
typedef Point Vector;
Vector operator+(Vector a, Vector b) { return Vector(a.x+b.x, a.y+b.y); }
Vector operator-(Vector a, Vector b) { return Vector(a.x-b.x, a.y-b.y);}
Vector operator*(Vector a, ld x) { return Vector(a.x*x, a.y*x); }
ld Dot(Vector a,Vector b) { return a.x*b.x + a.y*b.y; }
ld Cross(Vector a, Vector b) { return a.x*b.y-a.y*b.x; }
Point GetLineIntersection(Point p, Vector v, Point q, Vector w) {
return p + v*(Cross(w,p-q)/Cross(v,w));
}
bool OnSegment(Point p,Point a1,Point a2) {
return dcmp(Cross(a1-p,a2-p)) == 0 && dcmp(Dot(a1-p,a2-p)) < 0;
}
bool SegmentProperIntersection(Point a1, Point a2,Point b1,Point b2) {
if (OnSegment(a1, b1,b2) || OnSegment(a2, b1,b2)) return true;
double c1 = Cross(a2-a1,b1-a1), c2 = Cross(a2-a1,b2-a1),c3 = Cross(b2-b1,a1-b1),
c4 = Cross(b2-b1,a2-b1);
return dcmp(c1)*dcmp(c2) < 0 && dcmp(c3)*dcmp(c4) < 0;
}
bool up(Point a) {
return dcmp(a.y) > 0 || (dcmp(a.y) == 0 && dcmp(a.x) >= 0);
}
ld PolygonArea(deque<Point> &P) {
ld area = 0;
for (int i = 1;i < sz(P); ++i) {
area += Cross(P[i]-P[0], P[(i+1)%sz(P)] - P[0]);
}
return abs(area/2);
}
ld Length(Vector v) { return sqrt(Dot(v,v)); }
ld DistanceToLine(Point p, Point a, Point b) {
Vector v1 = b-a, v2 = p-a;
return fabs(Cross(v1,v2)) / Length(v1);
}
bool linecmp(pair<Point,Vector> a, pair<Point,Vector> b ) {
if (Cross(a.second,b.second) == 0 &&
dcmp(DistanceToLine(a.first,b.first,b.first+b.second)) == 0) return 1;
return 0;
}
ld solve(vector<pair<Point,Vector>> A) {
sort(A.begin(), A.end(), [&](auto x,auto y) {
auto a = x.second; auto b = y.second;
if (up(a) != up(b)) return up(a) > up(b);
if (Cross(a,b) == 0) {
Vector c = x.first - y.first;
if (Cross(b, c) > 0) return false;
else return true;
}
return Cross(a,b) > 0;
});
// cout << "DEG" _ Cross(A[1].second,A[2].second) << endl;
// Vector c = A[1].first - A[2].first;
// cout << Cross(A[2].second,c) << endl;
// for (auto [a,b] : A) {
// cout << a.x _ a.y _ b.x _ b.y _ up(b) << endl;
// }
deque<Point> P = {A[0].first, A[0].first +A[0].second};
for (int i = 1;i < sz(A); ++i) {
if (linecmp(A[i],A[i-1])) continue;
auto [x,v] = A[i];
auto y = x + v;
Point a = P[sz(P)-2], b = P[sz(P)-1];
while (!SegmentProperIntersection(a,b, x,y)) {
P.pop_back();
a = P[sz(P)-2], b = P.back();
break;
}
P.pop_back();
Point nx = GetLineIntersection(a,b-a,x,v);
P.push_back(nx); P.push_back(y);
}
// for (auto a : P) {
// cout << a.x _ a.y << endl;
// }
auto a = P[0], b = P[1];
auto x = P[sz(P)-2], y = P[sz(P)-1];
while (!SegmentProperIntersection(a,b,x,y)) {
P.pop_front();
if (sz(P) < 2) {
cout << 0 << endl;
exit(0);
}
a = P[0], b = P[1];
}
P.pop_front();
Point nx = GetLineIntersection(a,b-a,x,y-x);
P.push_front(nx); P.pop_back();
// for (auto a : P) {
// cout << a.x _ a.y << endl;
// }
return PolygonArea(P);
}
vector<Point> P;
int main() {
#ifdef LLOCAL
freopen("a.in", "r", stdin);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
// cout << Cross(Point(0,1e18),Point(0,-(1e18))) << endl;
cin >> n;
for (int i = 1;i <= n; ++i) {
int x,y; cin >> x >> y;
P.push_back(Point(x,y));
}
vector<pair<Point,Vector>> line;
for (int i = 0;i < n; ++i) {
int l = (i-1+n)%n;
Vector v = Vector(P[l]-P[i]);
// cout << v.x _ v.y << endl;
Point np = P[i] + v*(-(1e8));
// cout << np.x _ np.y << endl;
line.push_back({np, v*(1e10)});
}
ld ans = solve(line);
cout << fixed << setprecision(6) << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3688kb
input:
8 0 0 0 1 1 1 1 2 2 2 2 1 3 1 3 0
output:
1.000000
result:
ok "1.000000000"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3356kb
input:
8 0 0 0 2 1 2 1 1 2 1 2 2 3 2 3 0
output:
0
result:
ok "0.000000000"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
6 140 62 97 141 68 156 129 145 153 176 130 109
output:
48.803495
result:
ok "48.803495002"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
3 198 165 322 122 242 84
output:
4076.000000
result:
ok "4076.000000000"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
15 0 250 30 250 125 250 180 250 250 250 250 100 250 80 250 0 140 0 100 0 73 0 0 0 0 2 0 30 0 90
output:
62500.000000
result:
ok "62500.000000000"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
16 146 145 109 229 139 301 164 385 221 433 309 419 405 420 447 369 501 308 498 229 471 150 456 75 391 39 308 47 227 39 166 73
output:
114711.364656
result:
ok "114711.364655996"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3396kb
input:
6 160 210 200 210 200 300 280 300 200 170 200 80
output:
0
result:
ok "0.000000000"
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 3428kb
input:
8 198 165 230 113 246 117 281 161 266 36 247 68 228 79 200 30
output:
0
result:
wrong answer 1st numbers differ: expected 63.7023612500, found 0.0000000000, absolute error = 63.7023612500, error = 1.000000