QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#262742#876. Big BrotherFyindWA 1ms3764kbC++234.3kb2023-11-23 22:43:392023-11-23 22:43:39

Judging History

你现在查看的是最新测评结果

  • [2023-11-23 22:43:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3764kb
  • [2023-11-23 22:43:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> pii;
const int maxn = 1e4 + 5;
int n, m;
#define _ << " "<<
#define sz(x) ((int)x.size())
typedef long double ld;
const ld eps = 1e-17;
struct Point {
    ld x,y;
    Point(ld x=0,ld y = 0) : x(x), y(y) {}
};
ld dcmp(ld x) {
    if (fabs(x) < eps) return 0; else return x < 0 ? -1 : 1;
}
typedef Point Vector;
Vector operator+(Vector a, Vector b) { return Vector(a.x+b.x, a.y+b.y); }
Vector operator-(Vector a, Vector b) { return Vector(a.x-b.x, a.y-b.y);}
Vector operator*(Vector a, ld x) { return Vector(a.x*x, a.y*x); }

ld Dot(Vector a,Vector b) { return a.x*b.x + a.y*b.y; }
ld Cross(Vector a, Vector b) { return a.x*b.y-a.y*b.x; }

Point GetLineIntersection(Point p, Vector v, Point q, Vector w) {
    return p + v*(Cross(w,p-q)/Cross(v,w));
}
bool OnSegment(Point p,Point a1,Point a2) {
    return dcmp(Cross(a1-p,a2-p)) == 0 && dcmp(Dot(a1-p,a2-p)) < 0;
}
bool SegmentProperIntersection(Point a1, Point a2,Point b1,Point b2) {
    if (OnSegment(a1, b1,b2) || OnSegment(a2, b1,b2)) return true;
    double c1 = Cross(a2-a1,b1-a1), c2 = Cross(a2-a1,b2-a1),c3 = Cross(b2-b1,a1-b1),
    c4 = Cross(b2-b1,a2-b1);
    return dcmp(c1)*dcmp(c2) < 0 && dcmp(c3)*dcmp(c4) < 0;
}
bool up(Point a) {
    return dcmp(a.y) > 0 || (dcmp(a.y) == 0 && dcmp(a.x) >= 0); 
}

ld PolygonArea(deque<Point> &P) {
    ld area = 0;
    for (int i = 1;i < sz(P); ++i) {
        area += Cross(P[i]-P[0], P[(i+1)%sz(P)] - P[0]);
    }
    return abs(area/2);
}

ld Length(Vector v) { return sqrt(Dot(v,v)); }

ld DistanceToLine(Point p, Point a, Point b) {
    Vector v1 = b-a, v2 = p-a;
    return fabs(Cross(v1,v2)) / Length(v1);
}

bool linecmp(pair<Point,Vector> a, pair<Point,Vector> b ) {
    if (Cross(a.second,b.second) == 0 && 
    dcmp(DistanceToLine(a.first,b.first,b.first+b.second)) == 0) return 1;
    return 0;
}

ld solve(vector<pair<Point,Vector>> A) {
    sort(A.begin(), A.end(), [&](auto x,auto y) {
        auto a = x.second; auto b = y.second;
        if (up(a) != up(b)) return up(a) > up(b);
        if (Cross(a,b) == 0) {
            Vector c = x.first - y.first;
            if (Cross(b, c) > 0) return false;
            else return true;
        }
        return Cross(a,b) > 0;
    });
    // cout << "DEG" _ Cross(A[1].second,A[2].second) << endl;
    // Vector c = A[1].first - A[2].first;
    // cout << Cross(A[2].second,c) << endl;
    // for (auto [a,b] : A) {
    //     cout << a.x _ a.y _ b.x _ b.y _ up(b) << endl;
    // }

    deque<Point> P = {A[0].first, A[0].first +A[0].second};
    for (int i = 1;i < sz(A); ++i) {
        if (linecmp(A[i],A[i-1])) continue;
        auto [x,v] = A[i];
        auto y = x + v;
        Point a = P[sz(P)-2], b = P[sz(P)-1]; 
        while (!SegmentProperIntersection(a,b, x,y)) {
            P.pop_back();
            a = P[sz(P)-2], b = P.back();
            break;
        }
        P.pop_back();
        Point nx = GetLineIntersection(a,b-a,x,v);
        P.push_back(nx); P.push_back(y);
    }
    // for (auto a : P) {
    //     cout << a.x _ a.y << endl;
    // }
    auto a = P[0], b = P[1];
    auto x = P[sz(P)-2], y = P[sz(P)-1];
    while (!SegmentProperIntersection(a,b,x,y)) {
        P.pop_front();
        if (sz(P) < 2) {
            cout << 0 << endl;
            exit(0);
        }
        a = P[0], b = P[1];

    }
    P.pop_front();
    Point nx = GetLineIntersection(a,b-a,x,y-x);
    P.push_front(nx); P.pop_back();

    // for (auto a : P) {
    //     cout << a.x _ a.y << endl;
    // }

    return PolygonArea(P);
}
vector<Point> P;

int main() {
    #ifdef LLOCAL
    freopen("a.in", "r", stdin);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // cout << Cross(Point(0,1e18),Point(0,-(1e18))) << endl;
    cin >> n;
    for (int i = 1;i <= n; ++i) {
        int x,y; cin >> x >> y;
        P.push_back(Point(x,y));
    }
    vector<pair<Point,Vector>> line;
    for (int i = 0;i < n; ++i) {
        int l = (i-1+n)%n;
        Vector v = Vector(P[l]-P[i]);
        // cout << v.x _ v.y << endl;
        Point np = P[i] + v*(-(1e8));
        // cout << np.x _ np.y << endl;
        line.push_back({np, v*(1e10)});
    }
    ld ans = solve(line);
    cout << fixed << setprecision(6) << ans << endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3688kb

input:

8
0 0
0 1
1 1
1 2
2 2
2 1
3 1
3 0

output:

1.000000

result:

ok "1.000000000"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3356kb

input:

8
0 0
0 2
1 2
1 1
2 1
2 2
3 2
3 0

output:

0

result:

ok "0.000000000"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

6
140 62
97 141
68 156
129 145
153 176
130 109

output:

48.803495

result:

ok "48.803495002"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3524kb

input:

3
198 165
322 122
242 84

output:

4076.000000

result:

ok "4076.000000000"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

15
0 250
30 250
125 250
180 250
250 250
250 100
250 80
250 0
140 0
100 0
73 0
0 0
0 2
0 30
0 90

output:

62500.000000

result:

ok "62500.000000000"

Test #6:

score: 0
Accepted
time: 1ms
memory: 3764kb

input:

16
146 145
109 229
139 301
164 385
221 433
309 419
405 420
447 369
501 308
498 229
471 150
456 75
391 39
308 47
227 39
166 73

output:

114711.364656

result:

ok "114711.364655996"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3396kb

input:

6
160 210
200 210
200 300
280 300
200 170
200 80

output:

0

result:

ok "0.000000000"

Test #8:

score: -100
Wrong Answer
time: 0ms
memory: 3428kb

input:

8
198 165
230 113
246 117
281 161
266 36
247 68
228 79
200 30

output:

0

result:

wrong answer 1st numbers differ: expected 63.7023612500, found 0.0000000000, absolute error = 63.7023612500, error =   1.000000