QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#356649#5104. Guardians of the GalleryTadijaSebezCompile Error//C++146.8kb2024-03-18 06:47:302024-03-18 06:47:30

Judging History

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

  • [2024-03-18 06:47:30]
  • 评测
  • [2024-03-18 06:47:30]
  • 提交

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);
}

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(abs(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);
	}

	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);
	if(!hasR)return line(from,L);

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

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));
						}
					}
				}
			}
		}
	}
	printf("%.12lf\n",ans);
	return 0;
}

詳細信息

answer.code: In constructor ‘frac::frac(__int128, __int128)’:
answer.code:18:29: error: call of overloaded ‘abs(__int128&)’ is ambiguous
   18 |                 ll g=gcd(abs(a),b);
      |                          ~~~^~~
In file included from /usr/include/c++/13/cstdlib:79,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:42,
                 from answer.code:1:
/usr/include/stdlib.h:840:12: note: candidate: ‘int abs(int)’
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
In file included from /usr/include/c++/13/cstdlib:81:
/usr/include/c++/13/bits/std_abs.h:79:3: note: candidate: ‘constexpr long double std::abs(long double)’
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:75:3: note: candidate: ‘constexpr float std::abs(float)’
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:71:3: note: candidate: ‘constexpr double std::abs(double)’
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:61:3: note: candidate: ‘long long int std::abs(long long int)’
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:56:3: note: candidate: ‘long int std::abs(long int)’
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
answer.code: In function ‘int main()’:
answer.code:245:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  245 |         scanf("%i",&n);
      |         ~~~~~^~~~~~~~~
answer.code:248:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  248 |                 scanf("%i %i",&x,&y);
      |                 ~~~~~^~~~~~~~~~~~~~~
answer.code:252:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  252 |         scanf("%i %i",&sx,&sy);
      |         ~~~~~^~~~~~~~~~~~~~~~~
answer.code:254:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  254 |         scanf("%i %i",&ex,&ey);
      |         ~~~~~^~~~~~~~~~~~~~~~~