QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#384629 | #1196. Fun Region | stasio6 | WA | 59ms | 61816kb | C++14 | 7.0kb | 2024-04-10 07:59:52 | 2024-04-10 07:59:53 |
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) <= 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);
ld dpr = (v2-v1).dot(r-v1);
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 << "\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);
} 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";
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3880kb
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: 3764kb
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: 0ms
memory: 3572kb
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: 0
Accepted
time: 35ms
memory: 11904kb
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 ...
output:
80000.0000000000
result:
ok found '80000.0000000', expected '80000.0000000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
32 6000 9970 8929 9970 8929 9980 6000 9980 6000 9990 8806 9990 8806 10000 4000 10000 4000 60 3819 50 3819 40 4000 40 4000 30 323 30 323 20 4000 20 4000 10 1367 10 1367 0 6000 0 6000 9910 6139 9910 6139 9920 6000 9920 6000 9930 8225 9930 8225 9940 6000 9940 6000 9950 9296 9950 9296 9960 6000 9960
output:
19760000.0000000000
result:
ok found '19760000.0000000', expected '19760000.0000000', error '0.0000000'
Test #6:
score: -100
Wrong Answer
time: 59ms
memory: 61816kb
input:
1859 2843 492 2851 488 2866 481 2909 461 2940 447 2964 436 2975 431 2987 425 2995 422 2998 421 2999 420 3040 403 3054 397 3059 395 3059 394 3066 392 3073 389 3075 387 3076 388 3078 386 3092 381 3109 373 3126 367 3134 364 3145 359 3149 358 3163 352 3173 348 3174 348 3180 345 3203 336 3211 333 3217 33...
output:
36.6305331992
result:
wrong answer 1st numbers differ - expected: '2079546.0000000', found: '36.6305332', error = '0.9999824'