QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#616683#7670. Messengerucup-team1004WA 0ms6144kbC++171.9kb2024-10-06 10:07:212024-10-06 10:07:22

Judging History

你现在查看的是最新测评结果

  • [2024-10-06 10:07:22]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:6144kb
  • [2024-10-06 10:07:21]
  • 提交

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