QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#384638#1196. Fun Regionstasio6WA 0ms4020kbC++147.5kb2024-04-10 08:19:552024-04-10 08:19:56

Judging History

This is the latest submission verdict.

  • [2024-04-10 08:19:56]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 4020kb
  • [2024-04-10 08:19:55]
  • Submitted

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
 */

詳細信息

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'