QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#380636 | #1196. Fun Region | thomas_li | TL | 1ms | 3888kb | C++17 | 6.8kb | 2024-04-07 07:24:56 | 2024-04-07 07:24: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-9;
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) < EPS && sgn(oc)*sgn(od) < EPS)
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, P start) {
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;
break;
}
}
}
if (startid == -1)
return poly;
vector<P> res;
bool skip = false;
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 (!onRight(sa, sb, p) && !onLeft(sa, sb, p)) {
cerr << "mid\n";
if (!skip)
res.PB(p);
continue;
} else if (onLeft(sa, sb, p)) {
cerr << "l\n";
if (skip) {
auto si = segInter(sa, sb, p, prevv);
if (sz(si))
res.PB(si[0]);
cerr << "lineinter " << sz(si) << "\n";
}
skip = false;
} else {
if (!skip) {
auto si = segInter(sa, sb, p, prevv);
cerr << p << " " << prevv << " " << sz(si) << "seginter\n";
if (!si.empty())
res.PB(si[0]), skip = true;
}
}
if (!skip)
res.PB(p);
}
vector<P> rres;
for (auto p : res) {
if (rres.empty() || !cmp(rres.back(), p))
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 << v1 << " " << v2 << " " << v3 << "\n";
vector<P> vp = {v2, v3};
pair<ld, P> inter = {1000000000000000001ll, P(0, 0)};
for (int j = i + 3; j < i+n; j++) {
auto r = segInter(v1, v1 + (v2-v1)*1000000000, poly[j%n], poly[(j-1)%n]);
if (r.empty())
continue;
if ((v1-r[0]).dist2() < inter.FS)
inter = pair<ld, P>{(v1-r[0]).dist2(), r[0]};
}
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 << "\nrem\n";
for (auto p : vp) {
cerr << p << "\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, vleft);
} 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";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3868kb
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: 0
Accepted
time: 0ms
memory: 3888kb
input:
10 145 269 299 271 343 193 183 139 408 181 356 324 176 327 147 404 334 434 102 424
output:
12658.3130191311
result:
ok found '12658.3130191', expected '12658.3130191', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
6 144 401 297 322 114 282 372 178 197 271 368 305
output:
0
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: -100
Time Limit Exceeded
input:
2000 9274 7020 6000 7020 6000 7030 8801 7030 8801 7040 6000 7040 6000 7050 6517 7050 6517 7060 6000 7060 6000 7070 6182 7070 6182 7080 6000 7080 6000 7090 9928 7090 9928 7100 6000 7100 6000 7110 8928 7110 8928 7120 6000 7120 6000 7130 7778 7130 7778 7140 6000 7140 6000 7150 8627 7150 8627 7160 6000 ...