Submission #3822880

---

Source Code Expand

#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#define reg register
#define dmin(_,__) ((_)<(__)?(_):(__))
#define dmax(_,__) ((_)>(__)?(_):(__))
/*
	template of geom begin.
*/
const long double eps=1e-12,pi=acosl(-1.0);
inline bool fle(const long double&a,const long double&b){return a<b+eps;} //not strict, less or equal.
inline bool fls(const long double&a,const long double&b){return a+eps<b;} //strict, only less.
inline bool feq(const long double&a,const long double&b){return fabsl(a-b)<eps;} //equal.

struct geoVec{
	long double x,y;
	geoVec(){x=y=0;}
	geoVec(long double X,reg long double Y){x=X,y=Y;}
	inline long double theta(){return atan2l(y,x);} // slope.
	inline long double len2(){return x*x+y*y;} // module.
};
void inputVec(reg geoVec&a){
	scanf("%Lf%Lf",&a.x,&a.y);
	return;
}
void outputVec(reg geoVec&a){
	printf("(%.6Lf, %.6Lf)\n",a.x,a.y);
	return;
}
inline geoVec operator+(const geoVec&a,const geoVec&b){return geoVec(a.x+b.x,a.y+b.y);}
inline geoVec operator-(const geoVec&a,const geoVec&b){return geoVec(a.x-b.x,a.y-b.y);}
inline long double operator*(const geoVec&a,const geoVec&b){return a.x*b.x+a.y*b.y;} // dot product.
inline long double operator/(const geoVec&a,const geoVec&b){return a.x*b.y-a.y*b.x;} // cross product.
inline long double dis(const geoVec&A,const geoVec&B){return sqrtl((A-B).len2());}
struct geolineSeg{
	geoVec O,A;
	geolineSeg(){;}
	geolineSeg(geoVec o,geoVec a){O=o,A=a;}
	inline long double theta(){return A.theta();}
	inline long double len(){return sqrtl(A.len2());}
};
inline bool coincide(const geolineSeg&a,const geolineSeg&b){return a.A*b.A==0;}

struct geoCir{
	geoVec O;long double r;
	geoCir(){;}
	geoCir(geoVec o,long double R){O=o,r=R;}
};
inline bool operator <(const geoVec&A,const geoCir&B){ //inside.
	//printf("%.12Lf %.12Lf\n",(A-B.O).len2(),B.r*B.r);
	return fls((A-B.O).len2(),B.r*B.r);
}
inline bool operator==(const geoVec&A,const geoCir&B){ // on.
	return feq((A-B.O).len2(),B.r*B.r);
}
inline bool operator*(geolineSeg l,geoCir O){
	// should be strict.
	geoVec A=l.O,B=l.O+l.A; // line segment AB.
	//printf(" ");outputVec(A);printf(" ");outputVec(B);
	if(A<O||B<O)return 1; // the point inside the circle.
	long double a,b,c; //ax+by+c=0. avoid special judgment.
	a=-l.A.y;
	b=l.A.x;
	c=A/B;
	long double p1=a*O.O.x+b*O.O.y+c,
		   p2=O.r*O.r*(a*a+b*b);
	p1*=p1;
	//printf("%.8Lf, %.8Lf\n",p1,p2);
	if(fls(p1,p2)){
		p1=(O.O-A)*(B-A);p2=(O.O-B)*(A-B);
		return fls(0,p1)&&fls(0,p2);
	}
	else return 0;
}
/* template of geom over */

/* Graph */
struct Graph{
	int N,src,tgt,M;
	std::vector<int>u,v;
	std::vector<long double>w;
	void insert(reg int U,reg int V,reg long double W){
		++M;
		u.push_back(U);
		v.push_back(V);
		w.push_back(W);
	}
	void addedge(reg int U,reg int V,reg long double W){
		//printf(" >> %d %d %.3Lf\n",U,V,W);
		insert(U,V,W);
		insert(V,U,W);
		return;
	}
	long double dist[1000010];
	long double bellmanford(){
		for(reg int i=1;i<=N;++i)dist[i]=1e18;
		dist[src]=0;
		for(reg int i=1;i<=N;++i)
			for(reg int j=0;j<M;++j)
				dist[v[j]]=dmin(dist[v[j]],dist[u[j]]+w[j]);
		//for(reg int i=1;i<=N;++i)
		//	printf("      >> Dist[%d]: %.3Lf\n",i,dist[i]);
		return dist[tgt];
	}
}G;

int n;long double _v,_w[15];
geoCir a[15];
geoVec S,T,p[1000010];int pcnt;

/* main function */
void getPoint(){
	// 外公切线
	for(reg int i=1;i<=n;++i)
		for(reg int j=i+1;j<=n;++j){
			geoCir A=a[i],B=a[j]; // 已知圆 A，B.
			if(A.r<B.r)std::swap(A,B); // 不妨令 r_A>r_B.
			geoCir C=geoCir(A.O,A.r-B.r); // 作辅助圆 C，使 C 与 A 同心且半径为圆A，B半径之差。
			geoVec D=B.O; // 设圆 B 圆心为点 D.
			geolineSeg CD=geolineSeg(C.O,D-C.O); // 连接 CD.
			if(fle(CD.len(),C.r))continue; // 如果 B 与 A 内切或内含，则不存在切点.
			long double theta=acos(C.r/CD.len()); // 令 theta=acos(r_C/CD).
			long double alpha=CD.theta()+theta,beta=CD.theta()-theta; // 则将射线 CD 绕 C 旋转 alpha 或 beta，与圆 A 的交点为圆 A 上的公切点.
			// 类似的可以得到圆 B 上的公切点，所以通过旋转，易求得四个公切点.
			p[++pcnt]=geoVec(A.O.x+A.r*cosl(alpha),A.O.y+A.r*sinl(alpha));
			p[++pcnt]=geoVec(B.O.x+B.r*cosl(alpha),B.O.y+B.r*sinl(alpha));
			p[++pcnt]=geoVec(A.O.x+A.r*cosl(beta),A.O.y+A.r*sinl(beta));
			p[++pcnt]=geoVec(B.O.x+B.r*cosl(beta),B.O.y+B.r*sinl(beta));
		}
	// 内公切线
	for(reg int i=1;i<=n;++i)
		for(reg int j=i+1;j<=n;++j){
			geoCir A=a[i],B=a[j]; // 已知圆 A，B.
			if(A.r<B.r)std::swap(A,B); // 不妨令 r_A>r_B.
			geoCir C=geoCir(A.O,A.r+B.r); // 作辅助圆 C，使 C 与 A 同心且半径为圆A，B半径之和。
			geoVec D=B.O; // 设圆 B 圆心为点 D.
			geolineSeg CD=geolineSeg(C.O,D-C.O); // 连接 CD.
			if(fle(CD.len(),C.r))continue;
			long double theta=acos(C.r/CD.len()); // 令 theta=acos(r_C/CD).
			long double alpha=CD.theta()+theta,beta=CD.theta()-theta; // 则将射线 CD 绕 C 旋转 alpha 或 beta，与圆 A 的交点为圆 A 上的公切点.
			// 类似的可以得到圆 B 上的公切点，所以通过旋转，易求得四个公切点.
			p[++pcnt]=geoVec(A.O.x+A.r*cosl(alpha),A.O.y+A.r*sinl(alpha));
			p[++pcnt]=geoVec(B.O.x-B.r*cosl(alpha),B.O.y-B.r*sinl(alpha));
			p[++pcnt]=geoVec(A.O.x+A.r*cosl(beta),A.O.y+A.r*sinl(beta));
			p[++pcnt]=geoVec(B.O.x-B.r*cosl(beta),B.O.y-B.r*sinl(beta));
		}
	return;
}
void linkSeg(reg int u,reg int v){
	//printf(" %d %d\n",u,v);
	geoVec A=p[u],B=p[v];
	//outputVec(A);outputVec(B);
	geolineSeg AB=geolineSeg(A,B-A);
	for(reg int i=1;i<=n;++i)
		if(AB*a[i])return; // 如果线段与任何一个圆有交，不连边.
	G.addedge(u,v,AB.len());
	return;
}
bool inmid(reg long double&A,reg long double&B,reg long double&C){
	if(fls(A,B))return fls(A,C)&&fls(C,B);
	else return fls(C,B)||fls(A,C);
}
bool isArc(reg geoVec A,reg geoVec B,reg geoCir O,reg long double alpha,reg long double beta){
	for(reg int i=1;i<=n;++i){
		if(A<a[i]||B<a[i])return 0; // 弧端点在圆内，则必然有交点.
		reg long double disO=dis(O.O,a[i].O);
		if(fls(fabsl(a[i].r-O.r),disO)&&fls(disO,a[i].r+O.r)){ // 保证两圆相交，不相交必然没有交点.
			long double gamma=(a[i].O-O.O).theta();
			if(inmid(alpha,beta,gamma))return 0; // 判断圆心连线是否交当前弧.
		}
	}
	return 1;
}
long double lenArc(reg long double alpha,reg long double beta,reg long double r){
	if(alpha<=beta)return (beta-alpha)*r;
	else return (beta-alpha+2.0*pi)*r;
}
void getArc(){
	for(reg int i=1;i<=pcnt;++i)
		for(reg int j=i+1;j<=pcnt;++j)
			for(reg int k=1;k<=n;++k)
				if(p[i]==a[k]&&p[j]==a[k]){ // 如果两个点在该圆上.
					geoVec A=p[i],B=p[j];
					geoCir O=a[k];
					long double alpha=(A-O.O).theta(),beta=(B-O.O).theta(); // 两个点到圆心的幅角.
					if(isArc(A,B,O,alpha,beta))
						G.addedge(i,j,lenArc(alpha,beta,O.r));
					if(isArc(B,A,O,beta,alpha))
						G.addedge(j,i,lenArc(beta,alpha,O.r));
				}
	return;
}
long double solve(){
	n+=2;
	a[n]=geoCir(S,0);
	a[n-1]=geoCir(T,0);
	getPoint();
	//for(reg int i=1;i<=pcnt;++i)
	//	outputVec(p[i]);
	for(reg int i=1;i<=pcnt;i+=2)
		linkSeg(i,i+1);
	getArc();
	G.src=pcnt+1;
	G.tgt=pcnt+2;
	p[pcnt+1]=S;p[pcnt+2]=T;
	G.N=pcnt+2;
	for(reg int i=1;i<=pcnt;++i){
		if(feq(dis(S,p[i]),0))G.addedge(G.src,i,0);
		if(feq(dis(T,p[i]),0))G.addedge(i,G.tgt,0);
	}
	return G.bellmanford();
}
int main(){
	inputVec(S);inputVec(T);
	scanf("%Lf%d",&_v,&n);
	for(reg int i=1;i<=n;++i){
		inputVec(a[i].O);
		scanf("%Lf%Lf",&a[i].r,&_w[i]);
	}
	long double res=solve();
	if(res>1e17){puts("-1");return 0;}
	for(reg int i=1;i<=n;++i)
		if(T<geoCir(a[i].O,a[i].r+res/_v*_w[i])){ // 如果塔比人先到终点，GG.
			puts("-1");
			return 0;
		}
	printf("%.12Lf",res/_v);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void inputVec(geoVec&)’:
./Main.cpp:25:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%Lf%Lf",&a.x,&a.y);
                           ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:217:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%Lf%d",&_v,&n);
                       ^
./Main.cpp:220:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%Lf%Lf",&a[i].r,&_w[i]);
                                 ^

Judge Result