QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#190418#1950. SurveillanceSolitaryDream#AC ✓46ms3900kbC++201.7kb2023-09-28 20:40:142023-09-28 20:40:15

Judging History

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

  • [2023-09-28 20:40:15]
  • 评测
  • 测评结果:AC
  • 用时:46ms
  • 内存:3900kb
  • [2023-09-28 20:40:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
typedef double db;
const int N=4e5+50;
struct Point {
    int x,y;
    Point operator -(const Point &s) const{
        return {x-s.x,y-s.y};
    }
} A[6];
int det(Point a,Point b) {
    return a.x*b.y-a.y*b.x;
}
int LEN(Point a) {
    return abs(a.x+a.y);
}
int a,b,c,d;
bool g(db x,db y) {
    return max(0.0,a-x*b/(y+d))+max(0.0,2*a-x*b/(d-y))>=a;
}
db f(db x) {
    db L=0,R=d;
    FOR(_,1,100) {
        db mid=(L+R)/2;
        if(g(x,mid)) L=mid;
        else R=mid;
    }
    return L;
}
db F(db l,db r) {
    return (f(l)+f(r)+4*f((l+r)/2))*(r-l)/6;
}
db simpson(db L,db R) {
    db mid=(L+R)/2;
    if(fabs(F(L,R)-F(L,mid)-F(mid,R))<1e-12) return F(L,mid)+F(mid,R);
    return simpson(L,mid)+simpson(mid,R);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(12);
    int n;
    cin >> n;
    FOR(i,0,n-1) cin >> A[i].x >> A[i].y;
    if(n==4) {
        cout << LEN(A[0]-A[1])*LEN(A[2]-A[1]) << '\n';
    } else if(n==5) {
        while(1);
    } else {
        int p=0;
        for(int i=0; i<6; ++i) {
            int j=(i+1)%6;
            int k=(i+2)%6;
            if(det(A[j]-A[i],A[k]-A[j])<0) {
                p=j;
            }
        }
        int i=p;
        a=LEN(A[(i+2)%6]-A[(i+1)%6]);
        b=LEN(A[(i+1)%6]-A[(i+0)%6]);
        c=LEN(A[(i+0)%6]-A[(i+5)%6]);
        d=LEN(A[(i+5)%6]-A[(i+4)%6]);
        db res=a*d;
        res+=simpson(0,c);
        swap(a,d);
        swap(b,c);
        res+=simpson(0,c);
        cout << res << '\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3620kb

input:

4
-5 6
-5 -2
10 -2
10 6

output:

120

result:

ok found '120.0000000', expected '120.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 14ms
memory: 3876kb

input:

6
627 -788
444 -788
444 -986
-102 -986
-102 -993
627 -993

output:

1597.422688422667

result:

ok found '1597.4226884', expected '1597.4226884', error '0.0000000'

Test #3:

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

input:

6
340 110
340 375
-1000 375
-1000 -135
353 -135
353 110

output:

685643.438145167544

result:

ok found '685643.4381452', expected '685643.4381452', error '0.0000000'

Test #4:

score: 0
Accepted
time: 17ms
memory: 3860kb

input:

6
-182 -316
-182 -286
-672 -286
-672 -353
-580 -353
-580 -316

output:

4677.218525057692

result:

ok found '4677.2185251', expected '4677.2185251', error '0.0000000'

Test #5:

score: 0
Accepted
time: 8ms
memory: 3676kb

input:

6
-745 -431
-374 -431
-374 217
-587 217
-587 411
-745 411

output:

252676.393735565653

result:

ok found '252676.3937356', expected '252676.3937356', error '0.0000000'

Test #6:

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

input:

6
-920 341
-920 227
930 227
930 355
-448 355
-448 341

output:

229417.794630740478

result:

ok found '229417.7946307', expected '229417.7946307', error '0.0000000'

Test #7:

score: 0
Accepted
time: 46ms
memory: 3900kb

input:

6
-939 -133
957 -133
957 334
-69 334
-69 725
-939 725

output:

958691.104770130711

result:

ok found '958691.1047701', expected '958691.1047701', error '0.0000000'

Test #8:

score: 0
Accepted
time: 22ms
memory: 3868kb

input:

6
-175 108
-21 108
-21 -421
82 -421
82 171
-175 171

output:

9897.558343357930

result:

ok found '9897.5583434', expected '9897.5583434', error '0.0000000'

Test #9:

score: 0
Accepted
time: 34ms
memory: 3896kb

input:

6
-306 -342
-235 -342
-235 170
-89 170
-89 548
-306 548

output:

48748.232234588984

result:

ok found '48748.2322346', expected '48748.2322346', error '0.0000000'

Test #10:

score: 0
Accepted
time: 11ms
memory: 3872kb

input:

6
-349 185
-218 185
-218 392
-825 392
-825 -218
-349 -218

output:

284794.987926964066

result:

ok found '284794.9879270', expected '284794.9879270', error '0.0000000'

Test #11:

score: 0
Accepted
time: 42ms
memory: 3760kb

input:

6
-689 -621
551 -621
551 -30
-291 -30
-291 -506
-689 -506

output:

248993.473037456162

result:

ok found '248993.4730375', expected '248993.4730375', error '0.0000000'

Test #12:

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

input:

4
-836 -551
-719 -551
-719 790
-836 790

output:

156897

result:

ok found '156897.0000000', expected '156897.0000000', error '0.0000000'

Test #13:

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

input:

4
276 -742
276 772
-947 772
-947 -742

output:

1851622

result:

ok found '1851622.0000000', expected '1851622.0000000', error '0.0000000'