QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#485739 | #8082. Minimum Euclidean Distance | zttttt | WA | 122ms | 4108kb | C++23 | 4.7kb | 2024-07-21 03:41:17 | 2024-07-21 03:41:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5010;
double aa[N],bb[N],cc[N];
pair<double,double>p[N];
//struct S}{
// int x1,y1,x2,y1;
//}s[N];
double xx[N],yy[N];
signed main(){
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>p[i].first>>p[i].second;
}
for(int i=2;i<=n;i++){
xx[i]=p[i].first-p[i-1].first;
}
xx[1]=p[1].first-p[n].first;
//for(int i=1;i<=n;i++)cout<<i<<" "<<xx[i]<<endl;
for(int i=2;i<=n;i++){
yy[i]=p[i].second-p[i-1].second;
}
yy[1]=p[1].second-p[n].second;
//for(int i=1;i<=n;i++)cout<<i<<" "<<yy[i]<<endl;
for(int i=2;i<=n;i++){
aa[i]=p[i].second-p[i-1].second;
bb[i]=p[i-1].first-p[i].first;
cc[i]=p[i].first*p[i-1].second-p[i-1].first*p[i].second;
}
aa[1]=p[1].second-p[n].second;
bb[1]=p[n].first-p[1].first;
cc[1]=p[1].first*p[n].second-p[n].first*p[1].second;
// for(int i=2;i<=n;i++){
// bb[i]=p[i-1].second-xl[i]*p[i-1].first;
// }
// bb[1]=p[n].second-xl[1]*p[n].first;
for(int i=1;i<=q;i++){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
double r=0.5*sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
//cout<<r<<endl;
double yxx=(x1+x2)*0.5;
//cout<<yxx<<endl;
double yxy=(y1+y2)*0.5;
//cout<<yxy<<endl;
int cntl=0,cntz=0,cntf=0;
for(int j=1;j<n;j++){
double xlx=yxx-p[j].first;
// cout<<j<<" "<<p[j].first<<endl;
// cout<<j<<" "<<yxx<<endl;
// cout<<j<<" "<<xlx<<endl;
double xly=yxy-p[j].second;
double cj=xx[j+1]*xly-yy[j+1]*xlx;
// cout<<j<<" "<<cj<<endl;
if(cj<0){
cntf++;
}else if(cj>0){
cntz++;
}else{
cntl++;
}
}
//cout<<cntf<<" "<<cntl<<" "<<cntz<<endl;
double xlx=yxx-p[n].first;
double xly=yxy-p[n].second;
double cj=xx[1]*xly-yy[1]*xlx;
if(cj<0){
cntf++;
}else if(cj>0){
cntz++;
}else{
cntl++;
}
if(cntl>0){
cout<<fixed<<setprecision(9);
cout<<0.5*r*r<<endl;
}else if(cntz==n){
cout<<fixed<<setprecision(9);
cout<<0.5*r*r<<endl;
}else{
double jl=100000000;
// for(int j=1;j<=n;j++){
// jl=min(jl,sqrt((yxx-p[j].first)*(yxx-p[j].first)+(yxy-p[j].second)*(yxy-p[j].second)));
// }
// for(int j=1;j<=n;j++){
// jl=min(jl,)
// }
int flag=0;
for(int j=2;j<=n;j++){
double aaa=bb[j],bbb=-aa[j];
double ccc=aa[j]*yxy-bb[j]*yxx;
double jdx=1.0*(-cc[j]*bbb+bb[j]*ccc)/(aa[j]*bbb-bb[j]*aaa);
double jdy=1.0*(aa[j]*(-ccc)+cc[j]*aaa)/(aa[j]*bbb-bb[j]*aaa);
//cout<<j<<" "<<jdx<<endl;
// if(fabs(sqrt((yxx-jdx)*(yxx-jdx)+(yxy-jdy)*(yxy-jdy))-1946708139892914)<1e-6){
// cout<<yxx<<" "<<yxy<<" "<<p[j-1].first<<" "<<p[j-1].second<<" "<<p[j].first<<" "<<p[j].second<<" "<<jdx<<" "<<jdy<<endl;
// flag=1;
// }
if((jdx>min(p[j-1].first,p[j].first)||fabs(jdx-min(p[j-1].first,p[j].first))<1e-6)&&(jdx<max(p[j-1].first,p[j].first)||fabs(jdx-max(p[j-1].first,p[j].first))<1e-6)&&(jdy>min(p[j-1].second,p[j].second)||fabs(jdy-min(p[j-1].second,p[j].second))<1e-6)&&(jdy<max(p[j-1].second,p[j].second)||fabs(jdy-max(p[j-1].second,p[j].second))<1e-6)){
jl=min(jl,sqrt((yxx-jdx)*(yxx-jdx)+(yxy-jdy)*(yxy-jdy)));
// if(fabs(jl-1946966666535562.75)<1e-6){
// cout<<yxx<<" "<<yxy<<" "<<p[j-1].first<<" "<<p[j-1].second<<" "<<p[j].first<<" "<<p[j].second<<" "<<jdx<<" "<<jdy<<endl;
// flag=1;
// break;
// }
}
}
if(flag)continue;
double aaa=bb[1],bbb=-aa[1];
double ccc=aa[1]*yxy-bb[1]*yxx;
double jdx=1.0*(-cc[1]*bbb+bb[1]*ccc)/(aa[1]*bbb-bb[1]*aaa);
double jdy=1.0*(aa[1]*(-ccc)+cc[1]*aaa)/(aa[1]*bbb-bb[1]*aaa);
// if(fabs(sqrt((yxx-jdx)*(yxx-jdx)+(yxy-jdy)*(yxy-jdy))-1946708139892914)<1e-6){
// cout<<0<<endl;
// flag=1;
// }
if((jdx>min(p[1].first,p[n].first)||fabs(jdx-min(p[1].first,p[n].first))<1e-6)&&(jdx<max(p[1].first,p[n].first)||fabs(jdx-max(p[1].first,p[n].first))<1e-6)&&(jdy>min(p[1].second,p[n].second)||fabs(jdy-min(p[1].second,p[n].second))<1e-6)&&(jdy<max(p[1].second,p[n].second)||fabs(jdy-max(p[1].second,p[n].second))<1e-6)){
jl=min(jl,sqrt((yxx-jdx)*(yxx-jdx)+(yxy-jdy)*(yxy-jdy)));
// if(fabs(jl-1946966666535562.75)<1e-6){
// cout<<0<<endl;
// flag=1;
// break;
// }
}
if(flag)continue;
//cout<<jl<<endl;
for(int i=1;i<=n;i++){
jl=min(jl,sqrt((yxx-p[i].first)*(yxx-p[i].first)+(yxy-p[i].second)*(yxy-p[i].second)));
}
// if(fabs(0.5*r*r+jl*jl-1946966666535993)<1e-6){
// cout<<0.5*r*r<<endl;
// continue;
// }
cout<<0.5*r*r+jl*jl<<endl;
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3928kb
input:
4 3 0 0 1 0 1 1 0 1 0 0 1 1 1 1 2 2 1 1 2 3
output:
0.250000000 0.750000000 1.875000000
result:
ok Your answer is acceptable!^ ^
Test #2:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
48 10 -30 0 -29 -4 -28 -7 -27 -9 -25 -12 -22 -16 -21 -17 -17 -20 -14 -22 -12 -23 -9 -24 -5 -25 -4 -25 0 -24 3 -23 5 -22 8 -20 12 -17 13 -16 16 -12 18 -9 19 -7 20 -4 21 0 21 1 20 5 19 8 18 10 16 13 13 17 12 18 8 21 5 23 3 24 0 25 -4 26 -5 26 -9 25 -12 24 -14 23 -17 21 -21 18 -22 17 -25 13 -27 10 -28 ...
output:
589.5 51.4706 1051.250000000 66.625000000 174.125000000 562.675000000 272.394230769 287.385000000 689.625000000 436.250000000
result:
ok Your answer is acceptable!^ ^
Test #3:
score: -100
Wrong Answer
time: 122ms
memory: 4108kb
input:
5000 5000 -50000000 0 -49999885 -49450 -49999770 -85675 -49999604 -122394 -49999391 -157604 -49999130 -192731 -49998803 -229143 -49998399 -267196 -49997956 -303872 -49997469 -339362 -49996891 -377221 -49996257 -414903 -49995577 -451819 -49994843 -488600 -49994059 -524941 -49993173 -563137 -49992252 ...
output:
2.21479e+15 1.63265e+15 3.95474e+15 5.40511e+15 8.17275e+14 9.02261e+14 3194363161448624.000000000 1619744446324385.000000000 363457485421825.187500000 4776425533214309.000000000 8267595460255074.000000000 2467163193204921.500000000 1182580285938702.250000000 1785755073284987.000000000 2070106793477...
result:
wrong answer Except 11553906067411116.000000000000, but found 10000000000000420.000000000000!QAQ