QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#675129 | #7527. Doors of the Wardrobe | Crysfly | WA | 137ms | 56856kb | C++14 | 3.5kb | 2024-10-25 18:00:34 | 2024-10-25 18:00:36 |
Judging History
answer
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
inline int read()
{
int x;cin>>x;return x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 400005
#define inf 0x3f3f3f3f
int n,m;
typedef long double db;
const db eps = 1e-13;
int sgn(db x){return x<-eps?-1:x>eps;}
int cmp(db a,db b){return sgn(a-b);}
struct P{
db x,y;
P (db xx=0,db yy=0){x=xx,y=yy;}
P &operator +=(P o){return x+=o.x,y+=o.y,*this;}
P &operator -=(P o){return x-=o.x,y-=o.y,*this;}
friend P operator +(P a,P b){return a+=b;}
friend P operator -(P a,P b){return a-=b;}
friend db operator *(P a,P b){return a.x*b.y-a.y*b.x;}
friend db operator %(P a,P b){return a.x*b.x+a.y*b.y;}
friend P operator *(P a,db b){return P(a.x*b,a.y*b);}
friend bool operator <(P a,P b){return cmp(a.x,b.x)==0?a.y<b.y:a.x<b.x;}
db len(){
return sqrtl(x*x+y*y);
}
void in(){
long double xx,yy;cin>>xx>>yy;
x=xx,y=yy;
}
void out(){
// cout<<"("<<x<<","<<y<<")";
}
};
__float128 cross(P a,P b,P c){
return (b-a)*(c-a);
}
int cmp3(P a,P b,P c){
__float128 x1=(b.x-a.x),y1=(b.y-a.y);
__float128 x2=(c.x-a.x),y2=(c.y-a.y);
__float128 d=x1*y2-y1*x2;
return d<1e-15 ? -1: d>1e-15;
}
vector<P>convex(vector<P>a){
int n=a.size(),m=0;
if(n<=1)return a;
sort(a.begin(),a.end());
vector<P>st(n*2); int tp=0;
For(i,0,n-1){
while(tp>1 && cmp3(st[tp-2],st[tp-1],a[i])<=0) --tp;
st[tp++]=a[i];
}
int t=tp;
Rep(i,n-2,0){
while(tp>t && cmp3(st[tp-2],st[tp-1],a[i])<=0) --tp;
st[tp++]=a[i];
}
st.resize(tp-1);
return st;
}
vector<P>a;
P b[maxn],d[maxn],in1[maxn],in2[maxn];
db ql[maxn],qr[maxn];
db res;
db gmax(vector<P>&a,P b,P d){
int n=a.size();
db mx=0;
/*for(auto p:a) {
mx=max(mx,(p-b)%d);
}*/
if(a[0]%d>a[n-1]%d){
int l=0,r=n-1;
while(l+1<r){
int mid=l+r>>1;
if(a[mid]%d>a[l]%d && a[mid]%d>a[mid-1]%d) l=mid;
else r=mid-1;
}
For(i,max(0,l-1),min(n-1,r+1)) mx=max(mx,(a[i]-b)%d);
}else{
int l=0,r=n-1;
while(l+1<r){
int mid=l+r>>1;
if(a[mid]%d>a[r]%d && a[mid]%d>a[mid+1]%d) r=mid;
else l=mid;
}
For(i,max(0,l-1),min(n-1,r+1)) mx=max(mx,(a[i]-b)%d);
}
return mx;
}
void cmax(vector<P>&a,int l,int r){
For(i,l,r){
ql[i]=min(ql[i],-gmax(a,b[i],P(0,0)-d[i]));
qr[i]=max(qr[i],gmax(a,b[i],d[i]));
}
}
void solve(int l,int r){
if(l==r){
int i=l;
res+=(qr[i]-ql[i]);
in1[i]=b[i]+d[i]*ql[i];
in2[i]=b[i]+d[i]*qr[i];
return;
}
int mid=l+r>>1;
solve(mid+1,r);
vector<P>p;
For(i,mid+1,r) {
p.pb(in1[i]);
p.pb(in2[i]);
}
p=convex(p);
cmax(p,l,mid);
solve(l,mid);
}
void work()
{
n=read(),m=read();
For(i,1,n) {
b[i].in(),d[i].in();
db ls=d[i].len();
d[i].x/=ls,d[i].y/=ls;
}
a.resize(m);
For(i,0,m-1) a[i].in();
a=convex(a);
cmax(a,1,n);
solve(1,n);
printf("%.14lf\n",(double)res);
}
signed main()
{
// cout<<(4.5*sqrt(2))<<"\n";
int T=1;
while(T--)work();
return 0;
}
/*
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 12ms
memory: 55536kb
input:
3 4 -3 3 0.6 -0.3 4 -1 1 1 1 -4 1 0 -2 3 2 3 2 -2 -0.5 -2
output:
20.27523290755122
result:
ok answer is 20.2752329075512 (delta 1.7522e-16)
Test #2:
score: 0
Accepted
time: 8ms
memory: 54764kb
input:
5 3 0.5 0.4 1 1 0.5 0.4 3 4 0.5 0.35 1 1 0.4 0.4 1 0 0.5 0.3 0 1 0.5 0.4 0.6 0.4 0.5 0.5
output:
0.85981327522310
result:
ok answer is 0.859813275223096 (delta 3.8858e-15)
Test #3:
score: 0
Accepted
time: 8ms
memory: 54632kb
input:
5 3 0.5 0.4 1 1 0.5 0.4 3 4 0.5 0.35 1 1 0.4 0.4 1 0 0.5 0.3 0 1 0.5 0.4 0.5 0.5 0.6 0.4
output:
0.85981327522310
result:
ok answer is 0.859813275223096 (delta 3.8858e-15)
Test #4:
score: 0
Accepted
time: 0ms
memory: 55820kb
input:
5 12 0.7 -0.3 0 1 0.5 0 1 1 0.5 0.033333333333333 0 1 0.5 0.033333333333333 1 0 0.5 0.05 1 0 0.0 0 0.1 0 0.2 0 0.3 0 0.4 0 0.5 0 0.5 0.1 0.6 0 0.7 0 0.8 0 0.9 0 1.0 0
output:
3.41746212024588
result:
ok answer is 3.41746212024588 (delta 1.2995e-15)
Test #5:
score: 0
Accepted
time: 8ms
memory: 54156kb
input:
5 12 -0.3 0.7 1 0 0 0.5 1 1 0.033333333333333 0.5 1 0 0.033333333333333 0.5 0 1 0.05 0.5 0 1 0 0.6 0 0.4 0.1 0.5 0 0.3 0 0.8 0 0.5 0 0.9 0 1.0 0 0.1 0 0.0 0 0.7 0 0.2
output:
3.41746212024588
result:
ok answer is 3.41746212024588 (delta 1.2995e-15)
Test #6:
score: 0
Accepted
time: 8ms
memory: 55116kb
input:
10 12 0 0 1 1 0.6 0.2 0 1 0.4 0.6 -1 0 0.6 0 -1 1 0 0 0 1 0.4 0.5 1 0 0.5 0.3 1 0 0 0.3 1 0 0.3 0.3 1 0 0.3 0.3 0 1 0.2 0.2 0.6 0.2 0.6 0.6 0.2 0.6 0.2 0.2 0.6 0.2 0.6 0.6 0.2 0.6 0.2 0.2 0.6 0.2 0.6 0.6 0.2 0.6
output:
6.09705627484771
result:
ok answer is 6.09705627484772 (delta 8.7404e-16)
Test #7:
score: 0
Accepted
time: 17ms
memory: 54916kb
input:
11 3 0.4 0.6 -1 1.2 0.8 -0.1 -1 0.1 0.5 1.05 0 1 0.4 1.0 0 1 0.6 1.0 0 1 0.3 0.9 0 1 0.7 0.9 0 1 0.2 0.7 0 1 0.8 0.7 0 1 0.1 0.4 0 1 0.9 0.4 0 1 0 0 1 0 0.5 -0.1
output:
10.18103677372062
result:
ok answer is 10.1810367737206 (delta 1.7448e-16)
Test #8:
score: 0
Accepted
time: 8ms
memory: 56136kb
input:
8 3 -0.762220710020949 0.960848634814740 0.280390347859400 0.959886062419538 -0.543850971093615 0.734414501114893 -0.427256201232584 -0.904130598148465 -0.308587087111148 -0.723868828767586 -0.977369509658100 -0.211539219982217 -0.080679584211341 -0.623872645456952 0.831979117964964 0.55480694594628...
output:
13.02689813640200
result:
ok answer is 13.026898136402 (delta 1.3636e-16)
Test #9:
score: 0
Accepted
time: 3ms
memory: 54768kb
input:
9 3 0.898690498337619 -0.179746197104477 0.999614363528218 -0.027769123646145 0.110351463328162 -0.422616723450085 -0.279788827908685 -0.960061566659912 -0.300252996136536 -0.968309581066027 0.854696098517848 -0.519128673045874 0.952829435906291 0.237672663072341 -0.611183161853922 -0.79148919301923...
output:
19.90500280777368
result:
ok answer is 19.9050028077737 (delta 1.7848e-16)
Test #10:
score: 0
Accepted
time: 3ms
memory: 56100kb
input:
10 3 0.070342089497671 -0.460264862606530 0.571810294945788 -0.820385876642212 0.788475327551128 -0.311212069608293 0.964101929706117 -0.265532425773089 0.366813150247519 0.189414857841604 0.900950396708540 0.433922092858526 -0.025464690043421 0.481042370982425 0.621108238787538 0.783724795901114 0....
output:
21.33362181246093
result:
ok answer is 21.3336218124609 (delta 0)
Test #11:
score: 0
Accepted
time: 8ms
memory: 55072kb
input:
11 3 -0.775122867998075 -0.324462516766419 -0.870185763377592 -0.492723794041812 0.271867294126994 -0.314788596521751 0.875220126295877 -0.483724850019750 0.159838684607629 -0.014674090173325 0.920134803351038 0.391601766673933 -0.208305526915072 0.138678278167128 -0.855854780186333 0.51721619776666...
output:
5.48159239038212
result:
ok answer is 5.48159239038213 (delta 9.7218e-16)
Test #12:
score: 0
Accepted
time: 8ms
memory: 54784kb
input:
12 5 0.316035625860380 0.054167102894646 0.415233195457349 -0.909715006686313 0.012033693255599 -0.517127656466508 -0.998047008109908 0.062467348293813 -0.911778006353474 0.434138159295005 -0.826906371022239 0.562339624748987 0.591762739510491 -0.252317701851837 -0.881901192154716 0.471434287336094 ...
output:
20.42383119183782
result:
ok answer is 20.4238311918378 (delta 3.479e-16)
Test #13:
score: 0
Accepted
time: 4ms
memory: 54804kb
input:
15 7 0.383636462970281 0.091301273291054 -0.178083033367321 -0.984015463916443 0.028282065271478 -0.787867919130403 0.750256053487245 -0.661147377069398 0.149903266403460 0.601903906070213 0.428442456521616 0.903569068444534 0.093087745686689 0.006815105251976 0.803797260834196 -0.594903322797447 -0...
output:
5.75042689603733
result:
ok answer is 5.75042689603733 (delta 4.6336e-16)
Test #14:
score: 0
Accepted
time: 14ms
memory: 55188kb
input:
100 3 -0.578211107831801 0.287473638423979 0.834386001175380 0.551180552126577 -0.536512988104892 0.460257895201809 -0.429955857196671 -0.902849910484725 0.659448545647913 -0.913615255033808 0.093581854933560 0.995611589138653 -0.796157342487406 0.263458009987518 -0.997872466743782 -0.06519616641091...
output:
104.44401831208326
result:
ok answer is 104.444018312083 (delta 4.0819e-16)
Test #15:
score: 0
Accepted
time: 10ms
memory: 54656kb
input:
100 100 -0.174467648909083 -0.201801252266503 0.470131387603037 0.882596441410480 -0.472138238030407 -0.453553930266106 0.351835966244485 0.936061671502903 -0.688261644623982 -0.268241883678908 -0.148633790169310 -0.988892307796914 0.380541159594408 0.161158290178969 -0.474254880064852 -0.8803875900...
output:
295.94065105400369
result:
ok answer is 295.940651054004 (delta 3.8415e-16)
Test #16:
score: 0
Accepted
time: 4ms
memory: 55484kb
input:
100 5 0.743611279083013 0.006283944783222 0.667348844117210 -0.744745272059799 0.006486241371740 0.143827295110092 -0.880291809849029 0.474432639594622 -0.311493926810460 0.755585693216458 -0.375884911761184 0.926666354795666 0.139232497699456 0.557448352048095 -0.988388963963009 0.151944910793776 0...
output:
107.34246515548246
result:
ok answer is 107.342465155483 (delta 3.9716e-16)
Test #17:
score: 0
Accepted
time: 20ms
memory: 54228kb
input:
1000 3 0.814193108063829 0.938268846693299 0.189021563160450 -0.981972936826866 -0.894462915658156 0.056567325082831 -0.603914948132540 -0.797048766025060 0.850406232867379 0.328000667703139 0.426841712270211 0.904326352964589 0.409208076792267 0.609529714382619 -0.797872175099292 -0.602826668456468...
output:
2502.70277907738819
result:
ok answer is 2502.70277907739 (delta 3.634e-16)
Test #18:
score: 0
Accepted
time: 106ms
memory: 56856kb
input:
10000 3 -0.027344576727362 0.366422341172134 0.380069695570397 0.924957851206759 -0.036905642095206 0.485758207930430 0.688750742833412 -0.724998216719478 0.984393996844049 0.730489810857773 0.719598128519330 -0.694390764218158 0.770266818005228 -0.799441248474411 -0.946212639196676 0.32354542405118...
output:
48234.32776378002018
result:
ok answer is 48234.3277637802 (delta 3.0169e-15)
Test #19:
score: 0
Accepted
time: 19ms
memory: 54808kb
input:
1000 1000 0.409735024061885 0.151845763225521 0.773343465013364 0.633987290977606 -0.752839887714774 -0.843860968010812 0.524959030774212 0.851127496917236 0.670481080838583 -0.696163386521161 0.933753290400254 -0.357917298641318 0.444963577857897 -0.976462799285448 0.514989081978322 0.8571967367198...
output:
10299.70926827326366
result:
ok answer is 10299.7092682733 (delta 2.2959e-15)
Test #20:
score: 0
Accepted
time: 137ms
memory: 56512kb
input:
10000 10000 -0.450025351735280 -0.090008923269524 -0.722784354286953 0.691073640937052 0.704498372588649 -0.468600464166860 0.981463972996210 0.191646731541381 -0.325206146833855 0.469882180672171 0.992134534816577 0.125176135202735 -0.532144632997687 0.346217231979403 0.813791044230086 -0.581157583...
output:
57702.95169678692764
result:
ok answer is 57702.951696787 (delta 1.6392e-15)
Test #21:
score: -100
Wrong Answer
time: 13ms
memory: 55172kb
input:
1000 1000 0.961556216429425 -1.314762670245720 0.920163091307436 -0.946420876792685 0.327847561600822 1.689778414181223 0.489605901837277 0.293585039663264 1.527710134662603 -0.903485255055727 0.674735734675436 -0.748453599212006 -1.193128488735113 0.999735066938836 -0.632026828273573 -0.93181050745...
output:
2014.12457236724640
result:
wrong answer expected 2014.12457730204, found 2014.12457236725 (delta 2.4501e-09)