QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#384635 | #1196. Fun Region | stasio6 | WA | 32ms | 11784kb | C++14 | 7.5kb | 2024-04-10 08:17:28 | 2024-04-10 08:17:29 |
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);
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
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3804kb
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: 3920kb
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: 3624kb
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: 32ms
memory: 11784kb
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: 3892kb
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: 0
Accepted
time: 30ms
memory: 4820kb
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:
2079546.0000000019
result:
ok found '2079546.0000000', expected '2079546.0000000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 29ms
memory: 4808kb
input:
1844 9223 2327 9225 2330 9231 2340 9233 2343 9234 2344 9238 2350 9263 2392 9264 2393 9268 2399 9279 2417 9280 2419 9298 2451 9302 2457 9305 2461 9327 2498 9357 2552 9365 2566 9367 2568 9368 2571 9379 2591 9386 2603 9398 2626 9408 2644 9413 2655 9418 2663 9431 2689 9436 2698 9451 2728 9462 2749 9469 ...
output:
1418060.0000000000
result:
ok found '1418060.0000000', expected '1418060.0000000', error '0.0000000'
Test #8:
score: 0
Accepted
time: 30ms
memory: 4928kb
input:
1861 5509 29 5515 29 5550 33 5559 33 5578 36 5601 38 5612 40 5676 48 5686 49 5687 50 5689 50 5696 51 5699 52 5709 52 5722 55 5724 55 5745 58 5761 60 5763 60 5791 65 5798 66 5814 69 5819 69 5903 84 5913 86 5916 87 5941 92 5965 97 5974 98 5979 99 5986 100 5995 102 6038 111 6048 113 6050 114 6051 114 6...
output:
1027161.0000000000
result:
ok found '1027161.0000000', expected '1027161.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 31ms
memory: 4772kb
input:
1835 680 7513 663 7483 654 7468 651 7461 648 7457 643 7448 630 7425 614 7395 602 7373 600 7371 596 7363 577 7328 570 7313 560 7295 544 7262 539 7253 536 7248 517 7208 516 7206 512 7199 510 7195 499 7172 480 7132 468 7108 453 7075 453 7074 438 7039 437 7039 433 7031 415 6988 412 6984 409 6975 408 697...
output:
13822236.0000000037
result:
ok found '13822236.0000000', expected '13822236.0000000', error '0.0000000'
Test #10:
score: 0
Accepted
time: 30ms
memory: 4788kb
input:
1858 9984 5375 9983 5383 9981 5413 9981 5418 9979 5441 9978 5446 9977 5459 9974 5485 9972 5503 9972 5514 9971 5514 9969 5535 9969 5536 9965 5570 9964 5585 9955 5656 9952 5678 9950 5691 9948 5701 9946 5720 9945 5723 9945 5725 9944 5731 9941 5757 9939 5767 9935 5790 9935 5791 9930 5820 9929 5830 9927 ...
output:
2490324.5000000009
result:
ok found '2490324.5000000', expected '2490324.5000000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
20 2340 769 3619 197 3795 149 5653 45 6914 383 7134 480 8823 1781 8989 1989 9211 2308 9332 2507 9781 3542 9828 3709 9859 3830 9925 4147 9916 5905 772 2336 1565 1370 1853 1118 1864 1109 2045 969
output:
29346414.0000000000
result:
ok found '29346414.0000000', expected '29346414.0000000', error '0.0000000'
Test #12:
score: -100
Wrong Answer
time: 1ms
memory: 4024kb
input:
216 9573 7015 9508 7159 9409 7352 9380 7407 9371 7424 9321 7511 9294 7558 9275 7590 9270 7598 9180 7739 9112 7841 9075 7894 8977 8027 8913 8109 8797 8250 8780 8269 8704 8355 8640 8425 8612 8454 8596 8470 8594 8473 8560 8507 8479 8589 8431 8634 8372 8689 8340 8718 8105 8916 8034 8971 7977 9015 7840 9...
output:
11592880.6810820512
result:
wrong answer 1st numbers differ - expected: '36377905.1499908', found: '11592880.6810821', error = '0.6813208'