QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#616684#7670. Messengerucup-team1004WA 268ms8204kbC++172.0kb2024-10-06 10:08:532024-10-06 10:08:54

Judging History

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

  • [2024-10-06 10:08:54]
  • 评测
  • 测评结果:WA
  • 用时:268ms
  • 内存:8204kb
  • [2024-10-06 10:08:53]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

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