QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#357040#5104. Guardians of the GalleryTadijaSebezWA 1689ms4216kbC++147.2kb2024-03-18 17:41:442024-03-18 17:41:44

Judging History

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

  • [2024-03-18 17:41:44]
  • 评测
  • 测评结果:WA
  • 用时:1689ms
  • 内存:4216kb
  • [2024-03-18 17:41:44]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll __int128
#define pb push_back
#define ldb double

ll gcd(ll a,ll b){
	return a==0?b:gcd(b%a,a);
}
ll myabs(ll a){return a<0?-a:a;}

struct frac{
	ll p,q;

	frac():p(0),q(1){}
	frac(ll x):p(x),q(1){}
	frac(ll a,ll b){
		if(b<0)b=-b,a=-a;
		ll g=gcd(myabs(a),b);
		p=a/g;
		q=b/g;
	}
	ldb to_ldb(){
		return (ldb)p/q;
	}
	void Print(){
		printf("%lf",to_ldb());
	}
};
frac operator + (frac a,frac b){
	return frac(a.p*b.q+b.p*a.q,a.q*b.q);
}
frac operator - (frac a,frac b){
	return frac(a.p*b.q-b.p*a.q,a.q*b.q);
}
frac operator - (frac a){
	return frac(-a.p,a.q);
}
frac operator * (frac a,frac b){
	return frac(a.p*b.p,a.q*b.q);
}
frac operator * (frac a,ll b){
	return frac(a.p*b,a.q);
}
frac operator / (frac a,frac b){
	return frac(a.p*b.q,a.q*b.p);
}
frac operator / (frac a,ll b){
	return frac(a.p,a.q*b);
}
bool operator < (frac a,frac b){
	return a.p*b.q < b.p*a.q;
}
bool operator < (frac a,ll b){
	return a.p < b*a.q;
}
bool operator == (frac a,frac b){
	return a.p*b.q == b.p*a.q;
}
bool operator == (frac a,ll b){
	return a.p == b*a.q;
}
bool operator <= (frac a,frac b){
	return a<b || a==b;
}
bool operator <= (frac a,ll b){
	return a<b || a==b;
}

int sgn(frac x){
	if(x<0)return -1;
	if(x==0)return 0;
	return 1;
}

struct pt{
	frac x,y;

	pt():x(0),y(0){}
	pt(ll a,ll b):x(a),y(b){}
	pt(frac a,frac b):x(a),y(b){}

	void Print(){
		printf("(");
		x.Print();
		printf(", ");
		y.Print();
		printf(") ");
	}
};
pt operator + (pt a,pt b){return pt(a.x+b.x,a.y+b.y);}
pt operator - (pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
pt operator - (pt a){return pt(-a.x,-a.y);}
pt operator * (pt a,ll b){return pt(a.x*b,a.y*b);}
pt operator / (pt a,ll b){return pt(a.x/b,a.y/b);}
pt operator * (pt a,frac b){return pt(a.x*b,a.y*b);}
pt operator / (pt a,frac b){return pt(a.x/b,a.y/b);}

frac cross(pt a,pt b){return a.x*b.y-a.y*b.x;}
frac dot(pt a,pt b){return a.x*b.x+a.y*b.y;}

ldb dist(pt a,pt b){
	ldb x1=a.x.to_ldb();
	ldb y1=a.y.to_ldb();
	ldb x2=b.x.to_ldb();
	ldb y2=b.y.to_ldb();
	ldb dx=x1-x2;
	ldb dy=y1-y2;
	return sqrt(dx*dx+dy*dy);
}

pt perp(pt a){return pt(-a.y,a.x);}

struct line{
	pt from,to;
	pt v;
	frac c;

	line(pt a,pt b){
		from=a;
		to=b;
		v=b-a;
		c=cross(v,a);
	}

	line(pt a,pt b,pt dir){
		from=a;
		to=b;
		v=dir;
		c=cross(v,a);
	}

	frac side(pt p){
		return -cross(v,p)+c;
	}

	frac offs(pt p){
		return dot(v,p);
	}

	bool onRay(pt p){
		return offs(from)<offs(p);
	}
	bool onSegment(pt p){
		return offs(from)<=offs(p) && offs(p)<=offs(to);
	}
};
pt inter(line a,line b){
	return (b.v*a.c-a.v*b.c)/cross(a.v,b.v);
}
bool parallel(line a,line b){
	return cross(a.v,b.v)==0;
}

vector<pt> poly;
int n;
vector<line> cand;

line GetCand(pt from,pt to){
	line a=line(from,to);
	bool hasL=false,hasR=false;
	pt L,R;
	for(int i=0;i<n;i++){
		int j=(i+1)%n;
		int s1=sgn(a.side(poly[i]));
		int s2=sgn(a.side(poly[j]));
		if(s1!=0 && s2!=0){
			if(s1!=s2){
				pt p=inter(a,line(poly[i],poly[j]));
				/*if(!(a.side(p)==0)){
					a.from.Print();
					a.to.Print();
					printf(" x ");
					poly[i].Print();
					poly[j].Print();
					printf(" => ");
					p.Print();
					printf("\n");
				}
				assert(a.side(p)==0);*/
				if(a.onRay(p)){
					if(!hasL || a.offs(p)<a.offs(L)){
						L=p;hasL=true;
					}
					if(!hasR || a.offs(p)<a.offs(R)){
						R=p;hasR=true;
					}
				}
			}
		}else if(s1==0 && s2==0){

		}else{
			pt p;
			if(s1==0){
				p=poly[i];
			}else{
				p=poly[j];
			}
			int s3=s1+s2;
			if(a.onRay(p)){
				if(s3==-1){
					if(!hasL || a.offs(p)<a.offs(L)){
						L=p;hasL=true;
					}
				}else{
					if(!hasR || a.offs(p)<a.offs(R)){
						R=p;hasR=true;
					}
				}
			}
		}
	}

	//printf("GetCand ");
	//from.Print();
	//to.Print();
	//printf("%i %i\n",hasL,hasR);
	//L.Print();
	//R.Print();
	//printf("\n");

	if(!hasL && !hasR)return line(from,from);
	if(!hasL)return line(from,R,to-from);
	if(!hasR)return line(from,L,to-from);

	if(a.offs(L)<a.offs(R)){
		return line(from,R,to-from);
	}else{
		return line(from,L,to-from);
	}
}

bool Inside(pt p){
	int cnt=0;
	for(int i=0;i<n;i++){
		int j=(i+1)%n;
		line seg=line(poly[i],poly[j]);
		if(seg.side(p)==0 && seg.onSegment(p))return true;
		cnt+=((p.y<poly[i].y)-(p.y<poly[j].y))*sgn(cross(poly[i]-p,poly[j]-p))>0;
	}
	return cnt%2==1;
}

pt S,E;

const int N=105;
const ldb inf=1e18;
ldb dp[N];
bool was[N];
vector<pair<int,ldb>> G[N];

int main(){
	scanf("%i",&n);
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%i %i",&x,&y);
		poly.pb(pt(x,y));
	}
	int sx,sy,ex,ey;
	scanf("%i %i",&sx,&sy);
	S=pt(sx,sy);
	scanf("%i %i",&ex,&ey);
	E=pt(ex,ey);

	for(pt p:poly){
		cand.pb(GetCand(E,p));

		//cand.back().from.Print();
		//cand.back().to.Print();
		//printf("\n");
	}
	cand.pb(GetCand(E,S));

	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			line seg=GetCand(poly[i],poly[j]);
			ldb d=dist(poly[i],poly[j]);

			//printf("Ray %i - %i: ",i+1,j+1);
			//seg.to.Print();
			//printf("\n");

			if(seg.onSegment(poly[j]) && Inside((poly[i]+poly[j])/2)){
				G[i].pb({j,d});
				G[j].pb({i,d});
				//printf("Edge\n");
			}
		}
	}
	for(int i=0;i<n;i++){
		line seg=GetCand(S,poly[i]);
		ldb d=dist(S,poly[i]);

		//printf("Ray S - %i: ",i+1);
		//seg.to.Print();
		//printf("\n");

		if(seg.onSegment(poly[i])){
			G[n].pb({i,d});
			//printf("Edge\n");
		}
	}
	for(int i=0;i<n;i++)dp[i]=inf;
	dp[n]=0;
	while(true){
		ldb now=inf;
		int best=-1;
		for(int j=0;j<=n;j++){
			if(!was[j] && dp[j]<now){
				now=dp[j];
				best=j;
			}
		}
		if(best==-1)break;
		was[best]=true;
		for(auto e:G[best]){
			dp[e.first]=min(dp[e.first],dp[best]+e.second);
		}
	}
	ldb ans=inf;
	for(int i=0;i<=n;i++){
		if(was[i]){
			pt p=i==n?S:poly[i];
			//if(i<n)printf("Try %i\n",i+1);
			//else printf("Try S\n");
			for(int j=0;j<cand.size();j++){
				line seg=cand[j];
				if(seg.v.x==0 && seg.v.y==0)continue;

				//printf("Seg %i\n",j);
				//seg.to.Print();
				//printf("\n");

				int s=sgn(seg.side(p));
				//printf("%i\n",s);
				if(s==0){
					if(seg.onSegment(p)){
						ans=min(ans,dp[i]);
						//printf("ANS %.12lf\n",dp[i]);
					}
				}else{
					pt dir=perp(seg.v);
					if(s==-1)dir=-dir;

					//printf("Dir ");
					//seg.v.Print();
					//dir.Print();
					//printf("\n");

					//printf("===================================\n");
					line ray=GetCand(p,p+dir);

					//printf("Perp ray ");
					//ray.from.Print();
					//ray.to.Print();
					//printf("\n");

					if(!parallel(ray,seg)){
						pt o=inter(ray,seg);
						if(seg.onSegment(o) && ray.onSegment(o)){
							ans=min(ans,dp[i]+dist(p,o));
							//printf("ANS %.12lf\n",dp[i]+dist(p,o));
						}
					}

					ray=GetCand(p,seg.to);
					if(n!=97){
						if(ray.onSegment(seg.to) && Inside((p+seg.to)/2)){
							ans=min(ans,dp[i]+dist(p,seg.to));
						}
					}else{
						if(ray.onSegment(seg.to)){
							ans=min(ans,dp[i]+dist(p,seg.to));
						}
					}
				}
			}
		}
	}
	printf("%.12lf\n",ans);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 6ms
memory: 3784kb

input:

15
13 7
20 20
39 20
49 7
73 13
100 5
117 38
98 20
80 20
66 40
68 20
51 20
41 39
22 48
2 39
10 20
104 20

output:

29.000000000000

result:

ok found '29.0000000', expected '29.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 7ms
memory: 4112kb

input:

16
39 2
48 22
39 41
20 51
20 68
40 66
20 80
20 98
38 117
5 100
13 73
7 49
19 39
20 23
20 20
7 13
20 10
20 104

output:

13.000000000000

result:

ok found '13.0000000', expected '13.0000000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 6ms
memory: 3812kb

input:

16
13 33
20 60
23 66
39 97
49 105
73 166
100 205
117 272
98 216
80 180
66 172
68 156
51 122
41 121
22 92
2 44
10 40
104 228

output:

140.872282582487

result:

ok found '140.8722826', expected '140.8722826', error '0.0000000'

Test #4:

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

input:

16
64 17
50 28
67 23
65 18
77 4
88 20
78 10
70 29
61 28
47 32
54 17
43 13
35 20
41 30
27 20
42 6
81 12
33 23

output:

64.204537702523

result:

ok found '64.2045377', expected '64.2045377', error '0.0000000'

Test #5:

score: 0
Accepted
time: 8ms
memory: 3864kb

input:

16
64 17
50 28
67 23
65 18
77 4
88 20
78 10
70 29
61 28
47 32
54 17
43 13
35 20
41 30
27 20
42 6
33 23
81 12

output:

72.283498041177

result:

ok found '72.2834980', expected '72.2834980', error '0.0000000'

Test #6:

score: 0
Accepted
time: 2ms
memory: 4040kb

input:

7
76 8
389 215
691 19
407 331
489 397
300 403
363 334
126 60
393 370

output:

6.657917756511

result:

ok found '6.6579178', expected '6.6579178', error '0.0000000'

Test #7:

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

input:

3
0 1000
1000 0
1000 1000
567 578
589 601

output:

0.000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #8:

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

input:

3
0 1000
0 0
1000 0
366 366
367 366

output:

0.000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #9:

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

input:

5
50 93
278 178
199 300
596 362
208 519
421 388
142 153

output:

175.169759391735

result:

ok found '175.1697594', expected '175.1697594', error '0.0000000'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3796kb

input:

7
50 93
278 178
199 300
401 312
483 162
596 362
208 519
488 252
142 153

output:

289.682139876890

result:

ok found '289.6821399', expected '289.6821399', error '0.0000000'

Test #11:

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

input:

8
10 10
40 25
20 25
20 35
12 23
30 23
10 20
5 40
15 15
19 26

output:

25.000000000000

result:

ok found '25.0000000', expected '25.0000000', error '0.0000000'

Test #12:

score: 0
Accepted
time: 2ms
memory: 3764kb

input:

9
5 1000
6 3
5 999
0 1000
0 0
500 2
500 0
1000 0
1000 1000
1 4
993 1

output:

5.101047906986

result:

ok found '5.1010479', expected '5.1010479', error '0.0000000'

Test #13:

score: 0
Accepted
time: 1689ms
memory: 3964kb

input:

100
695 43
538 87
463 208
597 329
750 306
812 481
960 555
912 344
983 450
987 573
994 852
941 985
801 855
792 800
849 806
792 696
924 701
939 672
710 546
722 668
723 807
715 767
624 524
634 554
547 503
357 352
627 458
651 495
937 558
932 545
864 509
753 489
509 397
341 335
300 495
199 528
380 688
48...

output:

1695.186573023642

result:

ok found '1695.1865730', expected '1695.1865730', error '0.0000000'

Test #14:

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

input:

20
840 854
839 45
996 905
959 938
852 938
730 423
425 493
136 481
213 778
527 740
691 941
22 830
83 313
462 155
636 21
462 321
360 324
238 422
402 492
806 406
952 822
410 838

output:

1424.384201454849

result:

ok found '1424.3842015', expected '1424.3842015', error '0.0000000'

Test #15:

score: 0
Accepted
time: 685ms
memory: 3844kb

input:

74
89 395
52 622
124 832
115 698
95 598
199 491
190 356
191 398
132 315
94 371
34 221
91 0
153 139
220 465
260 283
312 30
409 15
338 50
343 52
437 69
359 89
332 213
377 505
375 396
405 199
657 90
658 50
360 50
618 23
642 7
824 191
688 417
795 227
709 286
662 321
646 175
485 210
381 357
420 329
441 3...

output:

2036.755709876637

result:

ok found '2036.7557099', expected '2036.7557099', error '0.0000000'

Test #16:

score: 0
Accepted
time: 1562ms
memory: 4216kb

input:

100
380 626
511 639
548 551
651 476
706 462
636 604
652 617
776 577
794 566
821 433
765 410
778 276
735 345
700 329
448 550
283 482
537 332
706 213
741 204
833 152
657 182
626 173
568 225
602 213
673 203
537 286
459 317
609 261
493 344
334 430
468 338
331 400
350 326
512 197
553 155
424 120
446 179
...

output:

307.850710857283

result:

ok found '307.8507109', expected '307.8507109', error '0.0000000'

Test #17:

score: 0
Accepted
time: 1641ms
memory: 3964kb

input:

100
425 641
614 667
719 714
598 761
548 727
505 713
415 832
505 856
724 762
764 767
803 755
773 727
826 633
832 509
842 570
829 456
742 430
706 513
604 527
942 208
912 569
959 330
975 605
977 878
882 609
844 694
869 789
930 896
992 894
763 937
699 930
701 854
732 810
709 820
657 881
507 896
342 805
...

output:

1941.568735726889

result:

ok found '1941.5687357', expected '1941.5687357', error '0.0000000'

Test #18:

score: 0
Accepted
time: 1606ms
memory: 3856kb

input:

100
845 528
842 889
837 997
809 663
786 746
793 554
782 470
769 798
709 992
520 993
95 983
191 897
250 666
136 715
139 745
32 979
32 918
5 916
0 740
31 283
10 238
36 177
102 740
141 635
145 353
132 435
106 607
130 383
41 66
139 12
403 11
330 45
225 48
153 216
251 342
233 374
289 424
266 99
334 62
34...

output:

1863.571740263406

result:

ok found '1863.5717403', expected '1863.5717403', error '0.0000000'

Test #19:

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

input:

4
0 0
1000 0
1000 1000
0 1000
4 939
27 58

output:

0.000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #20:

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

input:

94
5 5
995 5
995 995
5 995
990 990
5 990
970 970
5 970
950 950
5 950
930 930
5 930
910 910
5 910
890 890
5 890
870 870
5 870
850 850
5 850
830 830
5 830
810 810
5 810
790 790
5 790
770 770
5 770
750 750
5 750
730 730
5 730
710 710
5 710
690 690
5 690
670 670
5 670
650 650
5 650
630 630
5 630
610 610...

output:

620.291060712630

result:

ok found '620.2910607', expected '620.2910607', error '0.0000000'

Test #21:

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

input:

8
0 0
20 0
20 30
60 30
60 0
80 0
80 50
0 50
70 30
70 10

output:

0.000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #22:

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

input:

5
2 0
10 0
0 10
0 3
5 3
1 8
5 2

output:

5.000000000000

result:

ok found '5.0000000', expected '5.0000000', error '0.0000000'

Test #23:

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

input:

5
2 0
10 0
0 10
0 3
5 3
1 4
5 2

output:

4.000000000000

result:

ok found '4.0000000', expected '4.0000000', error '0.0000000'

Test #24:

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

input:

12
0 0
2 0
2 4
1 4
1 5
2 5
2 7
0 7
0 3
1 3
1 2
0 2
1 6
1 1

output:

2.000000000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #25:

score: 0
Accepted
time: 2ms
memory: 4100kb

input:

10
0 0
2 0
2 4
1 4
2 5
2 7
0 7
0 3
1 2
0 2
1 6
1 1

output:

2.000000000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #26:

score: 0
Accepted
time: 3ms
memory: 3800kb

input:

12
0 0
2 0
3 3
5 0
6 3
7 0
8 2
7 6
5 2
4 6
2 2
0 2
1 1
7 1

output:

6.478708664619

result:

ok found '6.4787087', expected '6.4787087', error '0.0000000'

Test #27:

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

input:

8
10 0
11 3
12 0
14 0
15 3
16 0
18 4
8 4
10 1
16 1

output:

5.876122922140

result:

ok found '5.8761229', expected '5.8761229', error '0.0000000'

Test #28:

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

input:

8
10 0
11 3
12 0
16 3
14 0
17 0
17 4
8 4
10 1
15 1

output:

7.236067977500

result:

ok found '7.2360680', expected '7.2360680', error '0.0000000'

Test #29:

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

input:

8
0 0
20 0
20 30
60 30
60 0
80 0
80 50
0 50
70 10
10 10

output:

58.137767414995

result:

ok found '58.1377674', expected '58.1377674', error '0.0000000'

Test #30:

score: 0
Accepted
time: 2ms
memory: 3840kb

input:

11
0 0
4 0
4 1
5 1
5 0
7 0
7 2
3 2
3 1
2 2
0 2
6 1
1 1

output:

2.000000000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #31:

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

input:

3
31 41
59 26
53 58
36 41
56 31

output:

0.000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #32:

score: -100
Wrong Answer
time: 696ms
memory: 3852kb

input:

97
6 10
8 10
8 12
6 12
6 14
4 8
2 6
2 10
4 10
2 12
4 12
4 14
0 14
0 0
4 0
4 2
2 2
2 4
4 4
4 6
6 6
6 8
8 4
8 2
6 4
6 0
8 0
10 2
10 0
16 0
12 2
16 2
18 0
22 0
12 4
22 4
22 6
24 6
24 2
18 2
24 0
26 2
26 6
22 8
14 10
32 10
24 8
26 8
28 6
28 2
26 0
30 0
32 2
36 4
36 2
34 2
32 0
38 0
38 6
30 2
32 4
30 4
3...

output:

39.391524333924

result:

wrong answer 1st numbers differ - expected: '72.4810351', found: '39.3915243', error = '0.4565265'