QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#755492 | #7527. Doors of the Wardrobe | ucup-team138# | WA | 1ms | 6092kb | C++17 | 3.5kb | 2024-11-16 17:29:25 | 2024-11-16 17:29:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
const ld eps=1e-11;
const ld inf=1e18;
const int maxn=(3e5)+10;
int n,m;
struct node {
ld x,y;
friend node operator + (node A,node B) { return (node){A.x+B.x,A.y+B.y}; }
friend node operator - (node A,node B) { return (node){A.x-B.x,A.y-B.y}; }
void get() { scanf("%Lf %Lf",&x,&y); }
friend ld operator * (node A,node B) { return A.x*B.y-A.y*B.x; }
void print() { printf("(%.5Lf %.5Lf)\n",x,y); }
} p[maxn],d[maxn];
ld ans;
vector<node> v[2];
bool cmp0(node A,node B) {
if (fabs(A.x-B.x)<eps) return A.y<B.y;
return A.x<B.x;
}
bool cmp1(node A,node B) {
if (fabs(A.x-B.x)<eps) return A.y>B.y;
return A.x<B.x;
}
void insert(vector<node> &vec,node A,int op) {
if (op==0) {
while ((int)vec.size()>1&&(A-vec.back())*(vec.back()-vec[(int)vec.size()-2])<0) vec.pop_back();
} else {
while ((int)vec.size()>1&&(A-vec.back())*(vec.back()-vec[(int)vec.size()-2])>0) vec.pop_back();
}
vec.push_back(A);
}
void chkmin(ld &x,ld y) { if (x>y) x=y; }
void chkmax(ld &x,ld y) { if (x<y) x=y; }
int main() {
// freopen("qwq.in","r",stdin);
scanf("%d %d",&n,&m);
for (int i=1;i<=n;i++) {
p[i].get();
d[i].get();
}
vector<node> vec(m);
for (int i=0;i<m;i++) vec[i].get();
sort(vec.begin(),vec.end(),cmp0);
for (node &A : vec) insert(v[0],A,0);
sort(vec.begin(),vec.end(),cmp1);
for (node &A : vec) insert(v[1],A,1);
// for (node &A : v[0]) A.print();
// puts("");
// for (node &A : v[1]) A.print();
vec.clear();
for (int i=n;i>=1;i--) {
if (fabs(d[i].y)<eps) {
ld now=p[i].x,l=v[0][0].x,r=v[0].back().x;
for (node &A : vec) chkmin(l,A.x),chkmax(r,A.x);
chkmin(l,now),chkmax(r,now);
ans+=r-l;
vec.push_back((node){l,p[i].y});
vec.push_back((node){r,p[i].y});
} else {
ld k=-d[i].x/d[i].y;
ld l=p[i].y-k*p[i].x,r=l;
for (node &A : vec) chkmin(l,A.y-k*A.x),chkmax(r,A.y-k*A.x);
for (int op=0;op<=1;++op) {
int L=0,R=(int)v[op].size()-2;
while (L<=R) {
int mid=(L+R)>>1;
ld t1=v[op][mid].y-k*v[op][mid].x;
ld t2=v[op][mid+1].y-k*v[op][mid+1].x;
chkmin(l,t1),chkmin(l,t2),chkmax(r,t1),chkmax(r,t2);
if (fabs(t1-t2)<eps||R-L<=1) break;
if (!op) {
if (t1>t2) R=mid;
else L=mid+1;
} else {
if (t1<t2) R=mid;
else L=mid+1;
}
}
// for (node &A : v[op]) chkmin(l,A.y-k*A.x),chkmax(r,A.y-k*A.x);
}
ans+=(r-l)/sqrtl(k*k+1.0);
if (fabs(k)<eps) {
vec.push_back((node){p[i].x,l});
vec.push_back((node){p[i].x,r});
} else {
ld t1=p[i].y-l-k*p[i].x;
ld t2=p[i].y-r-k*p[i].x;
t1/=k+1/k;
t2/=k+1/k;
vec.push_back((node){p[i].x+t1,p[i].y-t1/k});
vec.push_back((node){p[i].x+t2,p[i].y-t2/k});
}
}
// vec[(int)vec.size()-2].print();
// vec.back().print();
}
printf("%.15Lf\n",ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5928kb
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.275232907551224
result:
ok answer is 20.2752329075512 (delta 0)
Test #2:
score: 0
Accepted
time: 1ms
memory: 5868kb
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.859813275223096
result:
ok answer is 0.859813275223096 (delta 1.1102e-16)
Test #3:
score: 0
Accepted
time: 1ms
memory: 5944kb
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.859813275223096
result:
ok answer is 0.859813275223096 (delta 1.1102e-16)
Test #4:
score: 0
Accepted
time: 1ms
memory: 5872kb
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.417462120245875
result:
ok answer is 3.41746212024588 (delta 1.2995e-16)
Test #5:
score: 0
Accepted
time: 1ms
memory: 5944kb
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.417462120245875
result:
ok answer is 3.41746212024588 (delta 1.2995e-16)
Test #6:
score: 0
Accepted
time: 1ms
memory: 5808kb
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.097056274847714
result:
ok answer is 6.09705627484772 (delta 2.9135e-16)
Test #7:
score: 0
Accepted
time: 1ms
memory: 5864kb
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.181036773720619
result:
ok answer is 10.1810367737206 (delta 0)
Test #8:
score: 0
Accepted
time: 1ms
memory: 5944kb
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.026898136401998
result:
ok answer is 13.026898136402 (delta 0)
Test #9:
score: 0
Accepted
time: 0ms
memory: 5872kb
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.905002807773680
result:
ok answer is 19.9050028077737 (delta 1.7848e-16)
Test #10:
score: 0
Accepted
time: 1ms
memory: 5864kb
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.333621812460929
result:
ok answer is 21.3336218124609 (delta 0)
Test #11:
score: 0
Accepted
time: 0ms
memory: 5864kb
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.481592390382125
result:
ok answer is 5.48159239038213 (delta 1.6203e-16)
Test #12:
score: 0
Accepted
time: 1ms
memory: 5884kb
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.423831191837825
result:
ok answer is 20.4238311918378 (delta 1.7395e-16)
Test #13:
score: -100
Wrong Answer
time: 1ms
memory: 6092kb
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.729916488179284
result:
wrong answer expected 5.75042689603733, found 5.72991648817928 (delta 0.0035795)