QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#357037#5104. Guardians of the GalleryTadijaSebezWA 1581ms4192kbC++147.2kb2024-03-18 17:41:092024-03-18 17:41:09

Judging History

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

  • [2024-03-18 17:41:09]
  • 评测
  • 测评结果:WA
  • 用时:1581ms
  • 内存:4192kb
  • [2024-03-18 17:41:09]
  • 提交

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<50){
						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: 4176kb

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: 3ms
memory: 4184kb

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

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: 6ms
memory: 3896kb

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

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: 0ms
memory: 3888kb

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

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

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

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

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

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

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: -100
Wrong Answer
time: 1581ms
memory: 3936kb

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:

1066.000533953212

result:

wrong answer 1st numbers differ - expected: '1695.1865730', found: '1066.0005340', error = '0.3711603'