幾何コンテスト2013

Submission #3830687

Source codeソースコード

#include<functional>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cstring>
#include<cassert>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
#define double long double
const double eps=1e-12;
struct derPunkt
{
	double x,y;
	derPunkt():x(0),y(0){}
	derPunkt(double x,double y):x(x),y(y){}
	inline double theta(){return atan2l(y,x);}
	inline double sqrlen(){return x*x+y*y;}
};
istream&operator>>(istream&ist,derPunkt&b)
{
	ist >> b.x >> b.y;
	return ist;
}
ostream&operator<<(ostream&ost,derPunkt&b)
{
	ost << '(' << b.x << ',' << b.y << ')';
	return ost;
}
inline derPunkt operator+(const derPunkt a,const derPunkt b){return derPunkt(a.x+b.x,a.y+b.y);}
inline derPunkt operator-(const derPunkt a,const derPunkt b){return derPunkt(a.x-b.x,a.y-b.y);}
inline double operator*(const derPunkt a,const derPunkt b){return a.x*b.x+a.y*b.y;}
inline double operator/(const derPunkt a,const derPunkt b){return a.x*b.y-b.x*a.y;}
inline bool fle(double a,double b){return a<b+eps;}//not strict
inline bool fls(double a,double b){return a+eps<b;}//strict
inline bool feq(double a,double b){return fabs(a-b)<eps;}
inline double dis(derPunkt A,derPunkt B){return sqrtl((A-B).sqrlen());}
struct dieGerade
{
	derPunkt O,A;
	dieGerade(){}
	dieGerade(derPunkt O,derPunkt A):O(O),A(A){}
	inline double theta(){return atan2l(A.y,A.x);}
	inline double len(){return sqrtl(A.sqrlen());}
};
inline bool straight(const dieGerade a,const dieGerade b){return a.A*b.A==0;}
struct derKreis
{
	derPunkt O;
	double r;
	derKreis(){}
	derKreis(derPunkt O,double r):O(O),r(r){}
};
inline bool operator<(const derPunkt A,const derKreis B){return fls((A-B.O).sqrlen(),B.r*B.r);}//strict
inline bool operator==(const derPunkt A,const derKreis B){return feq((A-B.O).sqrlen(),B.r*B.r);}
inline bool operator*(derKreis O,dieGerade l)//return 1 => should be strict
{
	derPunkt A=l.O,B=l.O+l.A;
	if(A<O||B<O)return 1;//should be strict
	double a,b,c;//ax+by+c=0
	a=-l.A.y;
	b=l.A.x;
	c=A/B;
	double d1=a*O.O.x+b*O.O.y+c,d2=O.r*O.r*(a*a+b*b);
	d1=d1*d1;
	if(fls(d1,d2))//should be strict
	{
		d1=(O.O-A)*(B-A);
		d2=(O.O-B)*(A-B);
		return fls(0,d1)&&fls(0,d2);//should be strict
	}
	else return 0;
}
int n;
derKreis a[13];
derPunkt s,t,p[111111];
int cp;
double w[13],v;
const double pi=acos(-1);
namespace uno
{
	int main()
	{
		double a,b,c,x0,y0,r0,w,x1,y1,r1,t1,d1,x2,y2,r2,t2,d2,t3,r3,k;
		w=::w[1];
		r0=::a[1].r;
		s=s-::a[1].O;
		t=t-::a[1].O;
		x0=s.x;
		y0=s.y;
		a=v*v-w*w;
		double vx,vy;
		vx=v*cosl((t-s).theta());
		vy=v*sinl((t-s).theta());
		b=2*(x0*vx+y0*vy-r0*w);
		c=x0*x0+y0*y0-r0*r0;
		double s1=(-b+sqrtl(b*b-4*a*c))/(2*a),s2=(-b-sqrtl(b*b-4*a*c))/(2*a);
		if(fle(s1,0)&&fle(s1,0)||fle(dis(s,t)/v,s1)&&fle(dis(s,t)/v,s2))
			return printf("%.10LF",dis(s,t)/v);
		t1=sqrtl((s.sqrlen()-r0*r0)/(v*v-w*w));
		r3=sqrtl(t.sqrlen());
		k=sqrtl(v*v-w*w);
		r1=r0+t1*w;
		double gamma=acosl(w/v);
		d1=s.theta()-asinl(sinl(gamma)*v*t1/sqrtl(s.sqrlen()));
		x1=cosl(d1)*r1;
		y1=sinl(d1)*r1;
		assert(feq(x1*x1+y1*y1,r1*r1));
		double d3=t.theta();
		if(d3>d1)d3-=2*pi;
		double l=0,r=min(pi,d1-d3),res=1e18;
		if(fls(k/w*log(r3/r1),r));
		else
		{
			for(;r-l>eps;)
			{
				double mid=(l+r)/2;
				d2=d1-mid;
				r2=cosl(d2-d3)*r3-sinl(d2-d3)*r3*w/k;
				if(k/w*log(r2/r1)<mid)
					l=mid;
				else r=mid;
			}
			d2=d1-l;
			r2=cosl(d2-d3)*r3-sinl(d2-d3)*r3*w/k;
			t2=(r2-r0)/w;
			x2=cosl(d2)*r2;
			y2=sinl(d2)*r2;
			t3=t2+dis(t,derPunkt(x2,y2))/v;
			if(res>t3)res=t3;
		}
		
		
		d1=s.theta()+asinl(sinl(gamma)*v*t1/sqrt(s.sqrlen()));
		x1=cosl(d1)*r1;
		y1=sinl(d1)*r1;
		d3=t.theta();
		if(d3<d1)d3+=2*pi;
		assert(feq(x1*x1+y1*y1,r1*r1));
		l=0;
		r=min(pi,d3-d1);
		if(fls(k/w*log(r3/r1),r));
		else
		{
			for(;r-l>eps;)
			{
				double mid=(l+r)/2;
				d2=d1+mid;
				r2=cosl(d3-d2)*r3-sinl(d3-d2)*r3*w/k;
				if(k/w*log(r2/r1)<mid)
					l=mid;
				else r=mid;
			}
			d2=d1+l;
			r2=cosl(d3-d2)*r3-sinl(d3-d2)*r3*w/k;
			t2=(r2-r0)/w;
			x2=cosl(d2)*r2;
			y2=sinl(d2)*r2;
			t3=t2+dis(t,derPunkt(x2,y2))/v;
			if(res>t3)res=t3;
		}
		
		if(res>1e17)puts("Impossible");
		else printf("%.10LF",res);
		return 0;
	}
}
namespace dos
{
	struct derGraf
	{
		int s,t,m;
		int n;
		vector<int>u,v;
		vector<double>w;
		void ins(int a,int b,double c)
		{
			u.push_back(a);
			v.push_back(b);
			w.push_back(c+eps);
			++m;
		}
		double dis[111111];
		inline void cmin(double&a,const double b){if(a>b)a=b;}
		double bf()
		{
			for(int i=1;i<=n;++i)dis[i]=1e18;
			dis[s]=0;
			for(int j=0;j<n;++j)
			{
				for(int i=0;i<m;++i)
					cmin(dis[v[i]],dis[u[i]]+w[i]);
			}
			return dis[t];
		}
	}G;
	void AE(int a,int b,double c)
	{
		G.ins(a,b,c);
		G.ins(b,a,c);
	}
	void seg(int alpha,int beta)
	{
		derPunkt A=p[alpha],B=p[beta];
		dieGerade l=dieGerade(A,B-A);
		for(int j=1;j<=n;++j)
			if(a[j]*l)
				return;
		AE(alpha,beta,l.len());
	}
	bool dans(const double&a,const double&b,const double&c)
	{
		if(fls(a,b))return fls(a,c)&&fls(c,b);
		else return fls(c,b)||fls(a,c);
	};
	bool arc(derPunkt A,derPunkt B,derPunkt O,double r,const double&alpha,const double&beta)
	{
		for(int i=1;i<=n;++i)
		{
			if(A<a[i]||B<a[i])return false;
			
			if(fls(fabs(a[i].r-r),dis(O,a[i].O))&&fls(dis(O,a[i].O),a[i].r+r))
			{
				double gamma=(a[i].O-O).theta();
				if(dans(alpha,beta,gamma))return false;
			}
		}
		return true;
	}
	double dk(double alpha,double beta,double r)
	{
		if(alpha<=beta)return (beta-alpha)*r;
		else return (beta-alpha+2*pi)*r;
	}
	int main()
	{
		n+=2;
		a[n]=derKreis(s,0);
		a[n-1]=derKreis(t,0);
		for(int i=1;i<=n;++i)
			for(int j=i+1;j<=n;++j)
			{
				derKreis A=a[i];
				derKreis B=a[j];
				if(A.r<B.r)swap(A,B);
				derKreis C(A.O,A.r-B.r);
				derPunkt D=B.O;
				dieGerade l(C.O,D-C.O);
				if(fle(l.len(),C.r))continue;
				double theta=acos(C.r/l.len());
				double alpha=l.theta()+theta,beta=l.theta()-theta;
				p[++cp]=derPunkt(A.O.x+cosl(alpha)*A.r,A.O.y+sinl(alpha)*A.r);
				p[++cp]=derPunkt(B.O.x+cosl(alpha)*B.r,B.O.y+sinl(alpha)*B.r);
				p[++cp]=derPunkt(A.O.x+cosl(beta)*A.r,A.O.y+sinl(beta)*A.r);
				p[++cp]=derPunkt(B.O.x+cosl(beta)*B.r,B.O.y+sinl(beta)*B.r);
			}
		for(int i=1;i<=n;++i)
			for(int j=i+1;j<=n;++j)
			{
				derKreis A=a[i];
				derKreis B=a[j];
				if(A.r<B.r)swap(A,B);
				derKreis C(A.O,A.r+B.r);
				derPunkt D=B.O;
				dieGerade l(C.O,D-C.O);
				if(fle(l.len(),C.r))continue;
				double theta=acos(C.r/l.len());
				double alpha=l.theta()+theta,beta=l.theta()-theta;
				p[++cp]=derPunkt(A.O.x+cosl(alpha)*A.r,A.O.y+sinl(alpha)*A.r);
				p[++cp]=derPunkt(B.O.x-cosl(alpha)*B.r,B.O.y-sinl(alpha)*B.r);
				p[++cp]=derPunkt(A.O.x+cosl(beta)*A.r,A.O.y+sinl(beta)*A.r);
				p[++cp]=derPunkt(B.O.x-cosl(beta)*B.r,B.O.y-sinl(beta)*B.r);
			}
		for(int i=0;i<cp;i+=2)
			seg(i+1,i+2);
		for(int i=1;i<=cp;++i)
		{
			for(int j=i+1;j<=cp;++j)
			{
				for(int k=1;k<=n;++k)
				{
					if(p[i]==a[k]&&p[j]==a[k])
					{
						derPunkt A=p[i],B=p[j],O=a[k].O;
						double alpha=(A-O).theta(),beta=(B-O).theta();
						if(arc(A,B,O,a[k].r,alpha,beta))
							AE(i,j,dk(alpha,beta,a[k].r));
						if(arc(B,A,O,a[k].r,beta,alpha))
							AE(j,i,dk(beta,alpha,a[k].r));
					}
				}
			}
		}
		G.s=cp+1;
		G.t=cp+2;
		p[cp+1]=s;
		p[cp+2]=t;
		G.n=cp+2;
		for(int i=1;i<=cp;++i)
		{
			if(feq(dis(s,p[i]),0))AE(G.s,i,0);
			if(feq(dis(t,p[i]),0))AE(i,G.t,0);
		}
		double res=G.bf();
		if(res>1e17)return puts("Impossible");
		for(int i=1;i<=n;++i)
			if(t<derKreis(a[i].O,a[i].r+res/v*w[i]))return puts("Impossible");
		printf("%.10LF",G.bf()/v);
		return 0;
	}
}
int main()
{
	cin >> s >> t >> v >> n;
	for(int i=1;i<=n;++i)
		cin >> a[i].O >> a[i].r >> w[i];
	if(n==1&&w[1]>0)uno::main();
	else dos::main();
	return 0;
}

Submission

Task問題 D - 魔女
User nameユーザ名 alphaGem
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 250
Source lengthソースコード長 8028 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Subtask1 50 / 50 11_rand00.txt,11_rand01.txt,11_rand02.txt,11_rand03.txt,11_rand04.txt,11_rand05.txt,11_rand06.txt,11_rand07.txt,11_rand08.txt,11_rand09.txt,11_rand10.txt,11_rand11.txt,11_rand12.txt,11_rand13.txt,11_rand14.txt,11_rand15.txt,11_rand16.txt,11_rand17.txt,11_rand18.txt,11_rand19.txt,11_rand20.txt,11_rand21.txt,11_rand22.txt,11_rand23.txt,11_rand24.txt
Subtask2 100 / 100 11_rand00.txt,11_rand01.txt,11_rand02.txt,11_rand03.txt,11_rand04.txt,11_rand05.txt,11_rand06.txt,11_rand07.txt,11_rand08.txt,11_rand09.txt,11_rand10.txt,11_rand11.txt,11_rand12.txt,11_rand13.txt,11_rand14.txt,11_rand15.txt,11_rand16.txt,11_rand17.txt,11_rand18.txt,11_rand19.txt,11_rand20.txt,11_rand21.txt,11_rand22.txt,11_rand23.txt,11_rand24.txt,21_rand00.txt,21_rand01.txt,21_rand02.txt,21_rand03.txt,21_rand04.txt,21_rand05.txt,21_rand06.txt,21_rand07.txt,21_rand08.txt,21_rand09.txt,21_rand10.txt,21_rand11.txt,21_rand12.txt,21_rand13.txt,21_rand14.txt,21_rand15.txt,21_rand16.txt,21_rand17.txt,21_rand18.txt,21_rand19.txt,21_rand20.txt,21_rand21.txt,21_rand22.txt,21_rand23.txt,21_rand24.txt
Subtask3 100 / 100 11_rand00.txt,11_rand01.txt,11_rand02.txt,11_rand03.txt,11_rand04.txt,11_rand05.txt,11_rand06.txt,11_rand07.txt,11_rand08.txt,11_rand09.txt,11_rand10.txt,11_rand11.txt,11_rand12.txt,11_rand13.txt,11_rand14.txt,11_rand15.txt,11_rand16.txt,11_rand17.txt,11_rand18.txt,11_rand19.txt,11_rand20.txt,11_rand21.txt,11_rand22.txt,11_rand23.txt,11_rand24.txt,21_rand00.txt,21_rand01.txt,21_rand02.txt,21_rand03.txt,21_rand04.txt,21_rand05.txt,21_rand06.txt,21_rand07.txt,21_rand08.txt,21_rand09.txt,21_rand10.txt,21_rand11.txt,21_rand12.txt,21_rand13.txt,21_rand14.txt,21_rand15.txt,21_rand16.txt,21_rand17.txt,21_rand18.txt,21_rand19.txt,21_rand20.txt,21_rand21.txt,21_rand22.txt,21_rand23.txt,21_rand24.txt,31_rand00.txt,31_rand01.txt,31_rand02.txt,31_rand03.txt,31_rand04.txt,31_rand05.txt,31_rand06.txt,31_rand07.txt,31_rand08.txt,31_rand09.txt,31_rand10.txt,31_rand11.txt,31_rand12.txt,31_rand13.txt,31_rand14.txt,31_rand15.txt,31_rand16.txt,31_rand17.txt,31_rand18.txt,31_rand19.txt,31_rand20.txt,31_rand21.txt,31_rand22.txt,31_rand23.txt,31_rand24.txt
Subtask4 0 / 150 41_rand00.txt,41_rand01.txt,41_rand02.txt,41_rand03.txt,41_rand04.txt,41_rand05.txt,41_rand06.txt,41_rand07.txt,41_rand08.txt,41_rand09.txt,41_rand10.txt,41_rand11.txt,41_rand12.txt,41_rand13.txt,41_rand14.txt,41_rand15.txt,41_rand16.txt,41_rand17.txt,41_rand18.txt,41_rand19.txt,41_rand20.txt,41_rand21.txt,41_rand22.txt,41_rand23.txt,41_rand24.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
11_rand00.txt AC 3 ms 3712 KB
11_rand01.txt AC 3 ms 3712 KB
11_rand02.txt AC 3 ms 3712 KB
11_rand03.txt AC 3 ms 3712 KB
11_rand04.txt AC 3 ms 3712 KB
11_rand05.txt AC 3 ms 3712 KB
11_rand06.txt AC 3 ms 3712 KB
11_rand07.txt AC 3 ms 3712 KB
11_rand08.txt AC 3 ms 3712 KB
11_rand09.txt AC 3 ms 3712 KB
11_rand10.txt AC 3 ms 3712 KB
11_rand11.txt AC 3 ms 3712 KB
11_rand12.txt AC 3 ms 3712 KB
11_rand13.txt AC 3 ms 3712 KB
11_rand14.txt AC 3 ms 3712 KB
11_rand15.txt AC 3 ms 3712 KB
11_rand16.txt AC 3 ms 3712 KB
11_rand17.txt AC 3 ms 3712 KB
11_rand18.txt AC 3 ms 3712 KB
11_rand19.txt AC 3 ms 3712 KB
11_rand20.txt AC 3 ms 3712 KB
11_rand21.txt AC 3 ms 3712 KB
11_rand22.txt AC 3 ms 3712 KB
11_rand23.txt AC 3 ms 3712 KB
11_rand24.txt AC 3 ms 3712 KB
21_rand00.txt AC 3 ms 3712 KB
21_rand01.txt AC 4 ms 3840 KB
21_rand02.txt AC 6 ms 3840 KB
21_rand03.txt AC 66 ms 4608 KB
21_rand04.txt AC 3 ms 3712 KB
21_rand05.txt AC 22 ms 4224 KB
21_rand06.txt AC 3 ms 3712 KB
21_rand07.txt AC 4 ms 3840 KB
21_rand08.txt AC 10 ms 3968 KB
21_rand09.txt AC 10 ms 3968 KB
21_rand10.txt AC 3 ms 3712 KB
21_rand11.txt AC 10 ms 3968 KB
21_rand12.txt AC 62 ms 4608 KB
21_rand13.txt AC 3 ms 3712 KB
21_rand14.txt AC 3 ms 3712 KB
21_rand15.txt AC 16 ms 4224 KB
21_rand16.txt AC 7 ms 3840 KB
21_rand17.txt AC 3 ms 3712 KB
21_rand18.txt AC 4 ms 3840 KB
21_rand19.txt AC 47 ms 4224 KB
21_rand20.txt AC 4 ms 3840 KB
21_rand21.txt AC 6 ms 3840 KB
21_rand22.txt AC 8 ms 3968 KB
21_rand23.txt AC 10 ms 3840 KB
21_rand24.txt AC 3 ms 3712 KB
31_rand00.txt AC 58 ms 4224 KB
31_rand01.txt AC 29 ms 3968 KB
31_rand02.txt AC 40 ms 4608 KB
31_rand03.txt AC 39 ms 4224 KB
31_rand04.txt AC 34 ms 4224 KB
31_rand05.txt AC 39 ms 4224 KB
31_rand06.txt AC 25 ms 4224 KB
31_rand07.txt AC 34 ms 4224 KB
31_rand08.txt AC 31 ms 4224 KB
31_rand09.txt AC 39 ms 4352 KB
31_rand10.txt AC 62 ms 4352 KB
31_rand11.txt AC 32 ms 4224 KB
31_rand12.txt AC 36 ms 4352 KB
31_rand13.txt AC 39 ms 4608 KB
31_rand14.txt AC 36 ms 4224 KB
31_rand15.txt AC 29 ms 4224 KB
31_rand16.txt AC 31 ms 4224 KB
31_rand17.txt AC 36 ms 4224 KB
31_rand18.txt AC 26 ms 4224 KB
31_rand19.txt AC 34 ms 4224 KB
31_rand20.txt AC 6 ms 3840 KB
31_rand21.txt AC 20 ms 4608 KB
31_rand22.txt AC 11 ms 3968 KB
31_rand23.txt AC 51 ms 4608 KB
31_rand24.txt AC 3 ms 3712 KB
41_rand00.txt AC 3 ms 3712 KB
41_rand01.txt AC 3 ms 3712 KB
41_rand02.txt AC 3 ms 3712 KB
41_rand03.txt AC 3 ms 3712 KB
41_rand04.txt AC 3 ms 3712 KB
41_rand05.txt AC 3 ms 3712 KB
41_rand06.txt AC 3 ms 3712 KB
41_rand07.txt AC 3 ms 3712 KB
41_rand08.txt WA
41_rand09.txt AC 3 ms 3712 KB
41_rand10.txt WA
41_rand11.txt WA
41_rand12.txt AC 3 ms 3712 KB
41_rand13.txt WA
41_rand14.txt AC 3 ms 3712 KB
41_rand15.txt AC 3 ms 3712 KB
41_rand16.txt AC 3 ms 3712 KB
41_rand17.txt AC 3 ms 3712 KB
41_rand18.txt AC 3 ms 3712 KB
41_rand19.txt AC 3 ms 3712 KB
41_rand20.txt AC 3 ms 3712 KB
41_rand21.txt AC 3 ms 3712 KB
41_rand22.txt AC 3 ms 3712 KB
41_rand23.txt AC 3 ms 3712 KB
41_rand24.txt AC 3 ms 3712 KB