QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#380636#1196. Fun Regionthomas_liTL 1ms3888kbC++176.8kb2024-04-07 07:24:562024-04-07 07:24:56

Judging History

This is the latest submission verdict.

  • [2024-04-07 07:24:56]
  • Judged
  • Verdict: TL
  • Time: 1ms
  • Memory: 3888kb
  • [2024-04-07 07:24:56]
  • 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-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";
}

詳細信息

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 ...

output:


result: