QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#654966#7670. Messengersz051WA 193ms129988kbC++202.9kb2024-10-18 23:24:122024-10-18 23:24:12

Judging History

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

  • [2024-10-18 23:24:12]
  • 评测
  • 测评结果:WA
  • 用时:193ms
  • 内存:129988kb
  • [2024-10-18 23:24:12]
  • 提交

answer

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <cmath>
#define int long long
#define double long double
using namespace std;

void read(int &x){
	x=0;
	int f=1;
	char c=getchar();
	while(!('0'<=c && c<='9')){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	} 
	while('0'<=c && c<='9'){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	x*=f;
}
struct Vector{
	double x,y;
	Vector(){
		x=y=0;
	}
	Vector(double xx,double yy){
		x=xx;
		y=yy;
	}
	friend Vector operator+(Vector a,Vector b){
		return Vector(a.x+b.x,a.y+b.y);
	}
	friend Vector operator-(Vector a,Vector b){
		return Vector(a.x-b.x,a.y-b.y);
	}
	friend Vector operator*(Vector a,double c){
		return Vector(a.x*c,a.y*c);
	}
	friend double operator*(Vector a,Vector b){
		return a.x*b.y-a.y*b.x;
	}
	double length(){
		return sqrt(x*x+y*y);
	}
} pa[1000010],pb[1000010],sa[1000010],sb[1000010];
int n,m;
double da[1000010],db[1000010];
double getd(Vector a,Vector b){
//	printf("[%lf %lf]->[%lf %lf]\n",a.x,a.y,b.x,b.y);
	Vector ab=a-b,norm=Vector(ab.y,-ab.x);
	if(ab.length()<=1e-9){
		return a.length();
	}
	if((a*norm)*(norm*b)<0){
		return min(a.length(),b.length());
	}else{
		return abs((a*b))/(ab.length());
	}
}
bool chk(double t){
	int posa=1,posb=1,lsta=0,lstb=t;
	Vector cura=pa[0],curb=pb[0];
	for(int i=1;i<=m;i++){
		if(db[i]<t){
			curb=pb[i];
		}else{
			curb=curb+sb[i]*(t-db[i-1]);
			posb=i;
			break;
		}
	}
	double mn=4e18;
	while(1){
		if(posa==n+1 && posb==m+1){
			break;
		}
		if(da[posa]>db[posb]-t){
//			printf("[%lf]",db[posb]-t);
			if(getd(cura-curb,cura+sa[posa]*(db[posb]-t-lsta)-curb-sb[posb]*(db[posb]-lstb))<=t){
				return 1;
			}
			cura=cura+sa[posa]*(db[posb]-t-lsta);
			curb=curb+sb[posb]*(db[posb]-lstb);
			lsta=db[posb]-t;
			lstb=db[posb];
			posb++;
		}else{
//			printf("[%lf]",da[posb]);
			if(getd(cura-curb,cura+sa[posa]*(da[posa]-lsta)-curb-sb[posb]*(da[posa]+t-lstb))<=t){
				return 1;
			}
			cura=cura+sa[posa]*(da[posa]-lsta);
			curb=curb+sb[posb]*(da[posa]+t-lstb);
			lsta=da[posa];
			lstb=da[posa]+t;
			posa++;
		}
	}
	return 0;
}
signed main(){
	read(n);
	n--;
	for(int i=0;i<=n;i++){
		scanf("%Lf %Lf",&pa[i].x,&pa[i].y);
		if(i){
			sa[i]=(pa[i]-pa[i-1])*(1.0/(pa[i]-pa[i-1]).length());
			da[i]=da[i-1]+(pa[i]-pa[i-1]).length();
		}
	}
	read(m);
	m--;
	da[0]=db[0]=0;
	for(int i=0;i<=m;i++){
		scanf("%Lf %Lf",&pb[i].x,&pb[i].y);
		if(i){
			sb[i]=(pb[i]-pb[i-1])*(1.0/(pb[i]-pb[i-1]).length());
			db[i]=db[i-1]+(pb[i]-pb[i-1]).length();
		}
	}
	if((pa[0]-pb[m]).length()>db[m]){
		printf("impossible");
		return 0;
	}
	da[n+1]=db[m+1]=4e18;
	double ql=0,qr=db[m];
	while(ql<qr-1e-9){
		double mid=(ql+qr)/2;
		//printf("[%lf]\n",mid);
		if(chk(mid)){
			qr=mid;
		}else{
			ql=mid;
		}
	}
	printf("%.9Lf",ql);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 23ms
memory: 126872kb

input:

2
0 0
0 10
2
4 10
4 0

output:

4.000000000

result:

ok correct

Test #2:

score: 0
Accepted
time: 16ms
memory: 127512kb

input:

2
0 0
1 0
3
2 0
3 0
3 10

output:

5.000000000

result:

ok correct

Test #3:

score: 0
Accepted
time: 17ms
memory: 127808kb

input:

2
0 30000
0 0
2
0 0
30000 0

output:

impossible

result:

ok correct

Test #4:

score: 0
Accepted
time: 20ms
memory: 128448kb

input:

2
0 30000
0 0
2
30000 0
0 0

output:

0.000000000

result:

ok correct

Test #5:

score: 0
Accepted
time: 11ms
memory: 127396kb

input:

2
30000 0
0 0
2
30000 30000
0 30000

output:

impossible

result:

ok correct

Test #6:

score: 0
Accepted
time: 27ms
memory: 127492kb

input:

2
30000 0
0 0
2
0 30000
30000 30000

output:

29999.999999999

result:

ok correct

Test #7:

score: -100
Wrong Answer
time: 193ms
memory: 129988kb

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.400000000

result:

wrong answer read 3.400000000000 but expected 3.313708498985