QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#357031#5104. Guardians of the GalleryTadijaSebezWA 6ms3916kbC++147.0kb2024-03-18 17:37:022024-03-18 17:37:02

Judging History

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

  • [2024-03-18 17:37:02]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:3916kb
  • [2024-03-18 17:37:02]
  • 提交

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(ray.onSegment(seg.to)){
						ans=min(ans,dp[i]+dist(p,seg.to));
					}
				}
			}
		}
	}
	printf("%.12lf\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 3888kb

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

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

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:

42.318335567276

result:

wrong answer 1st numbers differ - expected: '64.2045377', found: '42.3183356', error = '0.3408825'