QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#616678#7670. Messengerucup-team1004WA 95ms7900kbC++171.9kb2024-10-06 10:02:592024-10-06 10:02:59

Judging History

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

  • [2024-10-06 10:02:59]
  • 评测
  • 测评结果:WA
  • 用时:95ms
  • 内存:7900kb
  • [2024-10-06 10:02:59]
  • 提交

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]);
	for(int i=0,j=0;i<n&&j<t.size();){
		if(sa[i+1]<t[j].first){
			vec nex=now+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*(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: 3792kb

input:

2
0 0
0 10
2
4 10
4 0

output:

4.000000000000001

result:

ok correct

Test #2:

score: 0
Accepted
time: 1ms
memory: 5860kb

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: 3612kb

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: 3832kb

input:

2
30000 0
0 0
2
30000 30000
0 30000

output:

impossible

result:

ok correct

Test #6:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

2
30000 0
0 0
2
0 30000
30000 30000

output:

30000.000000000000000

result:

ok correct

Test #7:

score: -100
Wrong Answer
time: 95ms
memory: 7900kb

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:

22786.000000000000000

result:

wrong answer read 22786.000000000000 but expected 3.313708498985