QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#616684 | #7670. Messenger | ucup-team1004 | WA | 268ms | 8204kb | C++17 | 2.0kb | 2024-10-06 10:08:53 | 2024-10-06 10:08:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
const int N=5e4+10;
const double eps=1e-9;
using vec=complex<double>;
auto dis(const vec &a){
return hypot(real(a),imag(a));
}
double dot(const vec &a,const vec &b){
return real(a)*real(b)+imag(a)*imag(b);
}
double cross(const vec &a,const vec &b){
return dot(a,b*vec(0,-1));
}
vec unit(const vec &a){
return a/dis(a);
}
int n,m;
vec a[N],b[N];
double sa[N],sb[N];
void input(int &n,vec *a,double *s){
scanf("%d",&n),n--;
for(int i=0,x,y;i<=n;i++){
scanf("%d%d",&x,&y),a[i]=vec(x,y);
}
for(int i=1;i<=n;i++)s[i]=s[i-1]+dis(a[i]-a[i-1]);
}
double calc(const vec &a,const vec &b){
if(dot(a-b,-b)<0)return dis(b);
if(dot(b-a,-a)<0)return dis(a);
return abs(cross(a,b))/dis(a-b);
}
bool chk(double mid){
vector<pair<double,vec>>t;
int cur=0;
for(;cur<m&&sb[cur+1]<mid;cur++);
for(int i=cur+1;i<=m;i++){
t.push_back({sb[i]-mid,unit(b[i]-b[i-1])});
}
double las=0;
vec now=b[cur]+unit(b[cur+1]-b[cur])*(mid-sb[cur])-a[0];
for(int i=0,j=0;i<n&&j<t.size();){
if(sa[i+1]<t[j].first){
vec nex=now+(t[j].second-unit(a[i+1]-a[i]))*(sa[i+1]-las);
if(calc(now,nex)<mid+eps)return 1;
now=nex,las=sa[++i];
}else{
vec nex=now+(t[j].second-unit(a[i+1]-a[i]))*(t[j].first-las);
if(calc(now,nex)<mid+eps)return 1;
now=nex,las=t[j++].first;
}
}
return 0;
}
int main(){
input(n,a,sa),input(m,b,sb);
debug(ary(a,0,n),ary(sa,0,n));
debug(ary(b,0,m),ary(sb,0,m));
if(dis(b[m]-a[0])>sb[m])puts("impossible"),exit(0);
// chk(1),exit(0);
double l=0,r=sb[m],mid;
for(int T=100;T--;){
mid=(l+r)/2;
if(chk(mid))r=mid;
else l=mid;
}
printf("%.15lf\n",r);
return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3844kb
input:
2 0 0 0 10 2 4 10 4 0
output:
3.999999999000001
result:
ok correct
Test #2:
score: 0
Accepted
time: 1ms
memory: 5944kb
input:
2 0 0 1 0 3 2 0 3 0 3 10
output:
4.999999995000002
result:
ok correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
2 0 30000 0 0 2 0 0 30000 0
output:
impossible
result:
ok correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
2 0 30000 0 0 2 30000 0 0 0
output:
0.000000000000000
result:
ok correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
2 30000 0 0 0 2 30000 30000 0 30000
output:
impossible
result:
ok correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
2 30000 0 0 0 2 0 30000 30000 30000
output:
29999.999999999003194
result:
ok correct
Test #7:
score: 0
Accepted
time: 268ms
memory: 8204kb
input:
50000 0 0 1 0 1 1 2 1 2 2 3 2 3 3 4 3 4 4 5 4 5 5 6 5 6 6 7 6 7 7 8 7 8 8 9 8 9 9 10 9 10 10 11 10 11 11 12 11 12 12 13 12 13 13 14 13 14 14 15 14 15 15 16 15 16 16 17 16 17 17 18 17 18 18 19 18 19 19 20 19 20 20 21 20 21 21 22 21 22 22 23 22 23 23 24 23 24 24 25 24 25 25 26 25 26 26 27 26 27 27 28 ...
output:
3.313708498398859
result:
ok correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 4088kb
input:
2 0 0 30000 30000 2 0 30000 30000 0
output:
0.000000000000000
result:
ok correct
Test #9:
score: 0
Accepted
time: 1ms
memory: 5652kb
input:
2 0 30000 0 0 2 1 0 0 0
output:
impossible
result:
ok correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 4024kb
input:
2 0 1 0 0 2 30000 0 0 0
output:
14999.499999999501597
result:
ok correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 4044kb
input:
2 0 0 15000 0 2 30000 0 15000 0
output:
0.000000000000000
result:
ok correct
Test #12:
score: 0
Accepted
time: 0ms
memory: 5920kb
input:
2 0 0 14999 0 2 30000 0 15000 0
output:
0.999999999499778
result:
ok correct
Test #13:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
2 0 0 15000 0 2 30000 0 15001 0
output:
impossible
result:
ok correct
Test #14:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
2 0 15000 0 0 2 0 15000 0 30000
output:
0.000000000000000
result:
ok correct
Test #15:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
2 0 14999 0 0 2 0 15000 0 30000
output:
impossible
result:
ok correct
Test #16:
score: 0
Accepted
time: 0ms
memory: 4092kb
input:
2 0 0 0 30000 2 0 30000 0 0
output:
0.000000000000000
result:
ok correct
Test #17:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
2 0 30000 0 15000 2 0 15000 0 0
output:
impossible
result:
ok correct
Test #18:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
2 0 0 30000 30000 2 1 1 30000 30000
output:
impossible
result:
ok correct
Test #19:
score: -100
Wrong Answer
time: 0ms
memory: 4092kb
input:
3 0 30000 15000 15000 0 0 3 30000 30000 15000 15000 30000 0
output:
42426.406871192848484
result:
wrong answer read 42426.406871192848 but expected 0.000000000000