QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#524043#8677. Carl’s Vacationucup-team052AC ✓1ms3992kbC++234.7kb2024-08-19 09:14:362024-08-19 09:14:40

Judging History

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

  • [2024-08-19 09:14:40]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3992kb
  • [2024-08-19 09:14:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using db=long double;
const db eps=1e-9;
struct Vec
{
	db x,y;
	Vec(db a=0,db b=0) {x=a,y=b;}
	db norm() {return x*x+y*y;}
	db abs() {return sqrt(x*x+y*y);}
};
Vec operator + (Vec x,Vec y) {return Vec(x.x+y.x,x.y+y.y);}
Vec operator - (Vec x,Vec y) {return Vec(x.x-y.x,x.y-y.y);}
Vec operator * (Vec x,db y) {return Vec(x.x*y,x.y*y);}
Vec operator / (Vec x,db y) {return Vec(x.x/y,x.y/y);}
db cross(Vec x,Vec y) {return x.x*y.y-x.y*y.x;}
int sgn(db x)
{
	if(x<-eps) return -1;
	else if(x>eps) return 1;
	else return 0;
}
int ccw(Vec x,Vec y,Vec z) {return sgn(cross(y-x,z-x));}
struct Seg
{
	Vec s,t;
	Seg(Vec a=0,Vec b=0) {s=a,t=b;}
	Seg() {}
};
int isintersect(Seg p,Seg q)
{
	if(max(p.s.x,p.t.x)<min(q.s.x,q.t.x)) return 0;
	if(max(q.s.x,q.t.x)<min(p.s.x,p.t.x)) return 0;
	if(max(p.s.y,p.t.y)<min(q.s.y,q.t.y)) return 0;
	if(max(q.s.y,q.t.y)<min(p.s.y,p.t.y)) return 0;
	if(ccw(q.s,p.s,p.t)*ccw(q.t,p.s,p.t)==1) return 0;
	if(ccw(p.s,q.s,q.t)*ccw(p.t,q.s,q.t)==1) return 0;
	return 1;
}
Vec r90(Vec x) {return Vec(-x.y,x.x);}
Vec a[10],b[10];
const db pi=acos(-1);
db dif(db x,db y)
{
	db v=x-y;
	while(v>=2*pi) v-=2*pi;
	while(v<0) v+=2*pi;
	if(v<pi) return v;
	else return 2*pi-v;
}
void print(Vec x) {printf("%.2Lf %.2Lf\n",x.x,x.y);}
int ok1[10],ok2[10];
int main() {
#ifdef xay5421
	freopen("b.in","r",stdin);
#endif
	Vec a1,b1,a2,b2; db h1,h2;
	cin>>a1.x>>a1.y>>b1.x>>b1.y>>h1;
	cin>>a2.x>>a2.y>>b2.x>>b2.y>>h2;
	a[0]=a1,a[1]=b1,a[2]=b1+r90(b1-a1),a[3]=a1+r90(b1-a1);
	b[0]=a2,b[1]=b2,b[2]=b2+r90(b2-a2),b[3]=a2+r90(b2-a2);
	a[4]=a[0],b[4]=b[0];
	
	// print(a[0]),print(a[1]),print(a[2]),print(a[3]);
	// print(b[0]),print(b[1]),print(b[2]),print(b[3]);
	db ans=1e100;
	Vec ca=(a[0]+a[2])/2,cb=(b[0]+b[2])/2;
	db La=(ca.x-a[0].x)*(ca.x-a[0].x)+(ca.y-a[0].y)*(ca.y-a[0].y)+h1*h1;
	db Lb=(cb.x-b[0].x)*(cb.x-b[0].x)+(cb.y-b[0].y)*(cb.y-b[0].y)+h2*h2;
	// cout<<sqrt(Lb)<<endl;
	db lena=sqrt(La-(a[1]-a[0]).norm()/4),lenb=sqrt(Lb-(b[1]-b[0]).norm()/4);
	// cout<<lena<<" "<<lenb<<endl;
	for(int i=0;i<4;i++)
	{
		if(isintersect(Seg(ca,cb),Seg(a[i],a[i+1]))) ok1[i]=ok1[(i+1)%4]=ok1[(i+3)%4]=1;
		if(isintersect(Seg(ca,cb),Seg(b[i],b[i+1]))) ok2[i]=ok2[(i+1)%4]=ok2[(i+3)%4]=1;
	}
	for(int i=0;i<4;i++) if(ok1[i]) for(int j=0;j<4;j++) if(ok2[j])
	{
		Vec da=r90(a[i+1]-a[i]); da=da/da.abs(); da=da*lena;
		Vec va=(a[i+1]+a[i])/2+da;
		Vec db=r90(b[j+1]-b[j]); db=db/db.abs(); db=db*lenb;
		Vec vb=(b[j+1]+b[j])/2+db;
		// printf("%d %d : \n",i,j),print(va),print(vb);
		// printf("%d %d %d %d\n",ccw(va,a[i],vb),ccw(va,vb,a[i+1]),ccw(vb,b[j],va),ccw(vb,va,b[j+1]));
		if(!isintersect(Seg(va,vb),Seg(a[i],a[i+1]))) continue;
		if(!isintersect(Seg(va,vb),Seg(b[j],b[j+1]))) continue;
		if(ccw(va,a[i],vb)>=0&&ccw(va,vb,a[i+1])>=0)
		{
			if(ccw(vb,b[j],va)>=0&&ccw(vb,va,b[j+1])>=0)
			{
				ans=min(ans,(va-vb).abs());
			}
		}
	}
	auto chka=[&](int id,Vec v)
	{
		return ccw(a[id],a[(id+3)%4],v)<=0&&ccw(a[id],v,a[(id+1)%4])<=0;
	};
	auto chkb=[&](int id,Vec v)
	{
		return ccw(b[id],b[(id+3)%4],v)<=0&&ccw(b[id],v,b[(id+1)%4])<=0;
	};
	for(int i=0;i<4;i++) for(int j=0;j<4;j++)
	{
		if(chka(i,b[j])) continue;
		if(chkb(j,a[i])) continue;
		db l=sqrt(La)+sqrt(Lb)+(a[i]-b[j]).abs();
		ans=min(ans,l);
	}
	for(int i=0;i<4;i++) if(ok1[i]) for(int j=0;j<4;j++)
	{
		Vec da=r90(a[i+1]-a[i]); da=da/da.abs(); da=da*lena;
		Vec va=(a[i+1]+a[i])/2+da;
		if(chkb(j,va)) continue;
		if(!isintersect(Seg(va,b[j]),Seg(a[i],a[i+1]))) continue;
		if(ccw(va,a[i],b[j])>=0&&ccw(va,b[j],a[i+1])>=0)
		{
			db tl=sqrt(Lb)+(va-b[j]).abs();
			ans=min(ans,tl);
		}
	}
	for(int i=0;i<4;i++) for(int j=0;j<4;j++) if(ok2[j])
	{
		Vec db=r90(b[j+1]-b[j]); db=db/db.abs(); db=db*lenb;
		Vec vb=(b[j+1]+b[j])/2+db;
		if(chka(i,vb)) continue;
		if(!isintersect(Seg(a[i],vb),Seg(b[j],b[j+1]))) continue;
		if(ccw(vb,b[j],a[i])>=0&&ccw(vb,a[i],b[j+1])>=0)
		{
			long double tl=sqrt(La)+(vb-a[i]).abs();
			ans=min(ans,tl);
		}
	}
	printf("%.10Lf\n",ans);
	return 0;
}
/*
6.40312 44.0028
0 0 : 
5.00 6.40
8.09 63.91
-1 -1 -1 1
0 1 : 
5.00 6.40
-11.91 25.09
-1 1 -1 1
0 2 : 
5.00 6.40
26.91 5.09
1 -1 1 -1
0 3 : 
5.00 6.40
46.91 43.91
1 -1 1 -1
1 0 : 
3.60 5.00
8.09 63.91
1 -1 -1 1
1 1 : 
3.60 5.00
-11.91 25.09
1 -1 -1 1
1 2 : 
3.60 5.00
26.91 5.09
1 1 1 -1
1 3 : 
3.60 5.00
46.91 43.91
1 -1 1 -1
2 0 : 
5.00 3.60
8.09 63.91
1 1 -1 1
2 1 : 
5.00 3.60
-11.91 25.09
1 -1 -1 1
2 2 : 
5.00 3.60
26.91 5.09
-1 1 1 -1
2 3 : 
5.00 3.60
46.91 43.91
-1 1 1 -1
3 0 : 
6.40 5.00
8.09 63.91
-1 1 -1 1
3 1 : 
6.40 5.00
-11.91 25.09
-1 1 -1 1
3 2 : 
6.40 5.00
26.91 5.09
-1 -1 1 -1
3 3 : 
6.40 5.00
46.91 43.91
-1 1 1 -1
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3988kb

input:

1 0 0 0 10000
99999 10000 10000 10000 10000

output:

76118.7000492205

result:

ok found '76118.7000492', expected '76118.7000492', error '0.0000000'

Test #2:

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

input:

10000 10000 10000 0 10000
0 0 0 10000 10000

output:

32360.6797749979

result:

ok found '32360.6797750', expected '32360.6797750', error '0.0000000'

Test #3:

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

input:

0 0 100 100 20
0 0 -5 -5 2

output:

107.3655550790

result:

ok found '107.3655551', expected '107.3655551', error '0.0000000'

Test #4:

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

input:

0 0 100 100 20
23 23 18 18 2

output:

88.0567570506

result:

ok found '88.0567571', expected '88.0567571', error '0.0000000'

Test #5:

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

input:

0 0 100 100 20
100 100 105 95 2

output:

107.3655550790

result:

ok found '107.3655551', expected '107.3655551', error '0.0000000'

Test #6:

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

input:

0 0 100 100 20
44 156 49 151 2

output:

77.7045202177

result:

ok found '77.7045202', expected '77.7045202', error '0.0000000'

Test #7:

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

input:

0 0 100 100 20
200 0 205 5 2

output:

224.5280351568

result:

ok found '224.5280352', expected '224.5280352', error '0.0000000'

Test #8:

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

input:

0 0 100 100 20
-29 171 -24 176 2

output:

84.3681957983

result:

ok found '84.3681958', expected '84.3681958', error '0.0000000'

Test #9:

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

input:

0 0 100 100 20
-100 100 -105 105 2

output:

107.3655550790

result:

ok found '107.3655551', expected '107.3655551', error '0.0000000'

Test #10:

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

input:

0 0 100 100 20
-69 69 -74 74 2

output:

83.2946124444

result:

ok found '83.2946124', expected '83.2946124', error '0.0000000'

Test #11:

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

input:

0 0 30 0 20
50 20 80 20 20

output:

72.8010988928

result:

ok found '72.8010989', expected '72.8010989', error '0.0000000'

Test #12:

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

input:

0 0 30 0 20
50 20 80 20 140

output:

186.8749482758

result:

ok found '186.8749483', expected '186.8749483', error '0.0000000'

Test #13:

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

input:

0 0 30 0 140
50 20 80 20 140

output:

302.2649537612

result:

ok found '302.2649538', expected '302.2649538', error '0.0000000'

Test #14:

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

input:

0 0 30 0 500
50 20 80 20 140

output:

661.3287930050

result:

ok found '661.3287930', expected '661.3287930', error '0.0000000'

Test #15:

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

input:

0 0 30 0 500
50 20 80 20 500

output:

1020.6458719614

result:

ok found '1020.6458720', expected '1020.6458720', error '0.0000000'

Test #16:

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

input:

0 0 30 0 500
50 20 80 20 2000

output:

2520.3614737461

result:

ok found '2520.3614737', expected '2520.3614737', error '0.0000000'

Test #17:

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

input:

1137 -1096 229 -599 6253
5792 -405 3433 -9660 2912

output:

16631.2672046379

result:

ok found '16631.2672046', expected '16631.2672046', error '0.0000000'

Test #18:

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

input:

-1458 4365 -759 -5184 408
8891 -5111 2941 -8564 6966

output:

14848.0979672057

result:

ok found '14848.0979672', expected '14848.0979672', error '0.0000000'

Test #19:

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

input:

2289 1693 -2539 850 7414
-4989 3660 8091 2109 6915

output:

18844.4706205017

result:

ok found '18844.4706205', expected '18844.4706205', error '0.0000000'

Test #20:

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

input:

5431 8457 6717 -6624 2204
-5504 -5607 4032 -674 7792

output:

20847.8621668110

result:

ok found '20847.8621668', expected '20847.8621668', error '0.0000000'

Test #21:

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

input:

4274 -9998 -3313 -2647 4590
-792 1334 5701 -8048 3257

output:

16956.4834717883

result:

ok found '16956.4834718', expected '16956.4834718', error '0.0000000'

Test #22:

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

input:

-1563 -4648 1926 -2970 5843
-1600 9113 -1007 5823 7516

output:

19666.6200192504

result:

ok found '19666.6200193', expected '19666.6200193', error '0.0000000'

Test #23:

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

input:

-6957 -1204 -2026 2849 1571
9178 1160 -3263 -6525 9297

output:

22798.2691656400

result:

ok found '22798.2691656', expected '22798.2691656', error '0.0000000'

Test #24:

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

input:

-5254 4877 5836 -1945 4282
8106 -8783 7076 -2291 6168

output:

17820.1271048619

result:

ok found '17820.1271049', expected '17820.1271049', error '0.0000000'

Test #25:

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

input:

2278 -7979 -200 -9432 528
-8604 1343 -5214 2428 8005

output:

22690.4150723923

result:

ok found '22690.4150724', expected '22690.4150724', error '0.0000000'

Test #26:

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

input:

5003 277 737 -3626 2886
3492 4353 -446 5788 2426

output:

10058.3916191793

result:

ok found '10058.3916192', expected '10058.3916192', error '0.0000000'

Test #27:

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

input:

-6582 -2629 -1742 6935 5531
-2010 1455 1794 -3461 9066

output:

20018.3757266857

result:

ok found '20018.3757267', expected '20018.3757267', error '0.0000000'

Test #28:

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

input:

-8174 -1075 -6736 -2685 6615
-2151 4184 -1716 -308 5064

output:

16260.3532322230

result:

ok found '16260.3532322', expected '16260.3532322', error '0.0000000'

Test #29:

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

input:

5291 1243 8982 5204 8450
-1177 -5306 -1390 2460 8858

output:

23316.8500582544

result:

ok found '23316.8500583', expected '23316.8500583', error '0.0000000'

Test #30:

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

input:

-4229 2060 9017 -2659 5812
9887 -9973 5460 -2671 4205

output:

18310.3049215940

result:

ok found '18310.3049216', expected '18310.3049216', error '0.0000000'

Test #31:

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

input:

0 0 8 0 3
0 8 8 8 3

output:

10.0000000000

result:

ok found '10.0000000', expected '10.0000000', error '0.0000000'

Test #32:

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

input:

0 0 8 0 2
8 8 16 8 2

output:

12.0000000000

result:

ok found '12.0000000', expected '12.0000000', error '0.0000000'

Test #33:

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

input:

0 0 8 0 2
10 10 18 10 2

output:

14.8284271247

result:

ok found '14.8284271', expected '14.8284271', error '0.0000000'

Test #34:

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

input:

0 0 8 0 100000
10 10 18 10 100000

output:

200002.8287471247

result:

ok found '200002.8287471', expected '200002.8287471', error '0.0000000'

Test #35:

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

input:

51412 80788 39091 71527 97605
6327 44899 20415 -12571 86627

output:

194757.4868334289

result:

ok found '194757.4868334', expected '194757.4868334', error '0.0000000'

Test #36:

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

input:

-43347 56743 17244 83573 86143
-90081 -3018 -22063 -95528 26489

output:

179973.3418451778

result:

ok found '179973.3418452', expected '179973.3418452', error '0.0000000'

Test #37:

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

input:

88637 -28248 308 -92620 47395
-57673 62668 -66785 923 49207

output:

210116.8218173325

result:

ok found '210116.8218173', expected '210116.8218173', error '0.0000000'

Test #38:

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

input:

59768 12643 57116 -71451 64957
-43638 42191 -37837 9851 1875

output:

171578.6515053421

result:

ok found '171578.6515053', expected '171578.6515053', error '0.0000000'

Test #39:

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

input:

-46206 -30845 -28470 3652 33497
74620 -92045 75046 -19320 48537

output:

147174.1317146147

result:

ok found '147174.1317146', expected '147174.1317146', error '0.0000000'

Test #40:

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

input:

65899 65734 27624 70256 81635
-97389 -56422 -91684 -53179 88643

output:

317109.4217967594

result:

ok found '317109.4217968', expected '317109.4217968', error '0.0000000'

Test #41:

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

input:

-25117 -50391 569 -34721 73972
-90107 -83510 -46359 -95477 83257

output:

174084.6702541819

result:

ok found '174084.6702542', expected '174084.6702542', error '0.0000000'

Test #42:

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

input:

6832 -56636 7968 -59867 82961
6289 -49692 -56413 -38910 90946

output:

184208.6118875315

result:

ok found '184208.6118875', expected '184208.6118875', error '0.0000000'

Test #43:

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

input:

-100000 -100000 -100000 100000 100000
100000 100000 100000 -100000 100000

output:

482842.7124746190

result:

ok found '482842.7124746', expected '482842.7124746', error '0.0000000'

Test #44:

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

input:

-79878 -52149 -90171 -65032 95613
-22921 39940 69440 26987 94207

output:

319596.9717576302

result:

ok found '319596.9717576', expected '319596.9717576', error '0.0000000'

Extra Test:

score: 0
Extra Test Passed