QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#384638 | #1196. Fun Region | stasio6 | WA | 0ms | 4020kb | C++14 | 7.5kb | 2024-04-10 08:19:55 | 2024-04-10 08:19:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int,k>
template<class A, class B> void cmx(A& x, B y){ x = max<A>(x,y); }
template<class A, class B> void cmn(A& x, B y){ x = min<A>(x,y); }
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef double ld;
const ld EPS = 1e-12;
int sgn(ld x) { return (x > EPS) - (x < -EPS);}
template<class T> struct Point {
typedef Point P;
T x,y;
Point(T _x=0, T _y=0) : x(_x), y(_y) {}
P operator+(P p) const { return P(x+p.x,y+p.y); }
P operator-(P p) const { return P(x-p.x,y-p.y); }
P operator*(T d) const { return P(x*d,y*d); }
P operator/(T d) const { return P(x/d,y/d); }
T dist2() const { return x*x + y*y; }
double dist() const { return sqrt((double)dist2()); }
T dot(P p) const { return x*p.x + y*p.y; }
T cross(P p) const { return x*p.y-y*p.x;}
T cross(P a, P b) const { return (a-*this).cross(b-*this); }
friend ostream& operator<<(ostream& os, P p) {
return os << "(" << p.x << "," << p.y << ")";
}
};
typedef Point<ld> P;
template<class P>
P lineInter(P s1, P e1, P s2, P e2) {
auto d = (e1-s1).cross(e2-s2);
auto p = s2.cross(e1, e2), q = s2.cross(e2, s1);
return (s1*p+e1*q) / d;
}
vector<P> segInter(P a, P b, P c, P d) {
auto oa = c.cross(d, a), ob = c.cross(d, b),
oc = a.cross(b, c), od = a.cross(b, d);
if (sgn(oa)*sgn(ob) <= 0 && sgn(oc)*sgn(od) <= 0)
return {(a*ob-b*oa) / (ob-oa)};
// set<P> s;
// if (onSegment(c, d, a)) s.insert(a);
// if (onSegment(c, d, b)) s.insert(a);
// if (onSegment(a, b, c)) s.insert(c);
// if (onSegment(a, b, d)) s.insert(d);
// return {all(s)};
return {};
}
bool onRight(P s, P e, P p) {
return s.cross(e, p) < -EPS;
}
bool onLeft(P s, P e, P p) {
return s.cross(e, p) > EPS;
}
bool onSegment(P s, P e, P p) {
return abs(p.cross(s, e)) < EPS && (s-p).dot(e-p) < EPS;
}
bool inPolygon(vector<P> p, P a, bool strict) {
int cnt = 0, n = sz(p);
rep(i,0,n) {
P q = p[(i+1)%n];
if (onSegment(p[i], q, a)) return !strict;
cnt ^= ((a.y<p[i].y) - (a.y<q.y)) * a.cross(p[i], q) > 0;
}
return cnt;
}
bool cmp(P p1, P p2) {
P p = p1-p2;
ld a = max(abs(p.x), abs(p.y));
return a < 1e-6;
}
vector<P> cutPolygon(vector<P> poly, P sa, P sb) {
int startid = -1;
for (int i = 0; i < sz(poly); i++) {
if (segInter(poly[i], poly[(i+1)%sz(poly)], sa, sb).size()) {
if (onLeft(sa, sb, poly[i])) {
startid = i;
break;
} else if (onLeft(sa, sb, poly[(i+1)%sz(poly)])) {
startid = (i + 1)%sz(poly);
break;
}
}
}
if (startid == -1)
return poly;
vector<P> res;
bool skip = false;
// cerr << "start v:" << poly[startid] << "\n";
for (int i = startid+1; i <= sz(poly) + startid; i++) {
P p = poly[i%sz(poly)], prevv = poly[(i+sz(poly)-1)%sz(poly)];
// cerr << "cut " << p << " " << prevv << "\n";
if (onSegment(sa, sb, p)) {
// cerr << "mid\n";
// if (!skip) // TODO
res.PB(p);
continue;
}
auto si = segInter(sa, sb, p, prevv);
if (!si.empty()) {
res.PB(si[0]);
if (onLeft(sa, sb, p)) {
skip = false;
} else {
skip = true;
}
}
if (!skip)
res.PB(p);
}
vector<P> rres;
for (auto p : res) {
if (rres.empty() || !cmp(rres.back(), p)) {
// if (rres.size() <= 1 || abs(rres[sz(rres)-2].cross(rres.back(), p)) > EPS) // TODO
rres.PB(p);
}
}
return rres;
}
ld polygonArea(vector<P> v) {
ld a = v.back().cross(v[0]);
rep(i,0,sz(v)-1) a += v[i].cross(v[i+1]);
return a/2;
}
signed main(){
cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
int n;
cin >> n;
vector<P> poly;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
poly.PB({x, y});
}
vector<vector<P>> sidePoly;
for (int i = 0; i < n; i++) {
P v1 = poly[i], v2 = poly[(i+1)%n], v3 = poly[(i+2)%n];
if (onRight(v1, v2, v3)) {
// cerr << "new\n";
// cerr << v1 << " " << v2 << " " << v3 << "\n";
vector<P> vp = {v2, v3};
pair<ld, P> inter = {1000000000000000001ll, P(0, 0)};
for (int j = i + 1; j < i+n; j++) {
auto v4 = poly[j%n], vprev = poly[(j-1)%n];
if (!onLeft(v1, v2, v4) && !onLeft(v1, v2, vprev))
continue;
if (abs((v1-v2).cross(v4-vprev)) < EPS)
continue;
auto r = lineInter(v1, v2, v4, vprev);
if (!onSegment(vprev, v4, r))
continue;
ld dpr = (v2-v1).dot(r-v1);
// cerr << "match " << r << " " << dpr << "def: " << (v2-v1).dot(v2-v1) << "\n";
if (dpr > (v2-v1).dot(v2-v1) + EPS && dpr < inter.FS) {
inter = pair<ld, P>{dpr, r};
}
}
// cerr << inter.SD << "\n";
for (int j = i + 3; j < 3*n; j++) {
P vprev = poly[(j-1)%n];
P v4 = poly[j%n];
if (onSegment(v4, vprev, inter.SD)) {
vp.PB(inter.SD);
break;
} else {
vp.PB(v4);
}
}
// cerr << "rem\n";
// for (auto p : vp) {
// cerr << p << "\n";
// }
// cerr << "\n";
sidePoly.PB(vp);
}
}
// cerr << "start\n\n";
vector<P> res = poly;
for (auto vp : sidePoly) {
P sa = vp[0], sb = vp.back();
P vleft, vright; int foundleft = 0;
// for (auto p : res) {
// cerr << p << "\n";
// }
// cerr << "\n";
// cerr << sa << " " << sb << "\n\n";
for (auto p : res) {
if (onLeft(sa, sb, p)) {
foundleft = 1;
vleft = p;
}
if (onRight(sa, sb, p)) {
vright = p;
}
}
if (foundleft) {
// cerr << "found left\n";
res = cutPolygon(res, sa, sb);
} else {
// cerr << "not left\n";
// cerr << vright << "\n";
// for (auto p : vp) {
// cerr << p << "\n";
// }
if (inPolygon(vp, vright, false)) {
// cerr << "zero!\n";
cout << "0\n";
return 0;
}
}
}
// cerr << "\n\n";
// for (auto p : res) {
// cerr << p << "\n";
// }
cout << fixed << setprecision(10) << polygonArea(res) << "\n";
}
/*
12
0 9
0 0
2 0
2 1
4 1
4 3
2 5
3 6
4 6
4 9
3 8
2 9
OUT: 11
16
6 5
5 6
5 8
3 8
3 6
2 5
0 5
0 3
2 3
3 2
3 0
5 0
5 2
6 3
8 3
8 5
OUT: ?
6
0 2
0 0
1 1
4 1
4 3
3 2
OUT: ?
12
4 3
2 3
2 2
3 2
3 1
1 1
1 4
5 4
5 5
0 5
0 0
4 0
OUT: ?
12
1 1
1 4
5 4
5 5
0 5
0 0
4 0
4 3
2 3
2 2
3 2
3 1
OUT: 2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4020kb
input:
4 10 0 20 10 10 30 0 10
output:
300.0000000000
result:
ok found '300.0000000', expected '300.0000000', error '0.0000000'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3788kb
input:
10 145 269 299 271 343 193 183 139 408 181 356 324 176 327 147 404 334 434 102 424
output:
19034.8957605285
result:
wrong answer 1st numbers differ - expected: '12658.3130191', found: '19034.8957605', error = '0.5037466'