QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#190418 | #1950. Surveillance | SolitaryDream# | AC ✓ | 46ms | 3900kb | C++20 | 1.7kb | 2023-09-28 20:40:14 | 2023-09-28 20:40:15 |
Judging History
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'