QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#616683 | #7670. Messenger | ucup-team1004 | WA | 0ms | 6144kb | C++17 | 1.9kb | 2024-10-06 10:07:21 | 2024-10-06 10:07:22 |
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;
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)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)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);
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
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3976kb
input:
2 0 0 0 10 2 4 10 4 0
output:
4.000000000000001
result:
ok correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3972kb
input:
2 0 0 1 0 3 2 0 3 0 3 10
output:
5.000000000000003
result:
ok correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
2 0 30000 0 0 2 0 0 30000 0
output:
impossible
result:
ok correct
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 6144kb
input:
2 0 30000 0 0 2 30000 0 0 0
output:
30000.000000000000000
result:
wrong answer read 30000.000000000000 but expected 0.000000000000