kmjp's blog

競技プログラミング参加記です

VolBIT Formulas Blitz : M-R

あと少し。
http://codeforces.com/contest/630/problem/M
http://codeforces.com/contest/630/problem/N
http://codeforces.com/contest/630/problem/O
http://codeforces.com/contest/630/problem/P
http://codeforces.com/contest/630/problem/Q
http://codeforces.com/contest/630/problem/R

M. Turn

3回以内で必ずベストな位置を経由する。
実際3回までまわしても良いし、最初からif文を書き連ねても良い。

void solve() {
	ll N;
	cin>>N;
	N=(N%360+360)%360;
	
	if(N<=45 || N>=315) cout<<0<<endl;
	else if(N>45&&N<=135) cout<<1<<endl;
	else if(N>135&&N<=225) cout<<2<<endl;
	else cout<<3<<endl;
}

N. Forecast

二次方程式を解くだけ。2個の実数解があることは確定しているので判別式の正負を気にする必要はない。

void solve() {
	ll a,b,c;
	
	cin>>a>>b>>c;
	double d=sqrt(b*b-4*a*c);
	double sm=(-b-d)/(2*a);
	double la=(-b+d)/(2*a);
	if(sm>la) swap(sm,la);
	
	_P("%.12lf\n",la);
	_P("%.12lf\n",sm);
}

O. Arrow

(vx,vy)の長さを正規化し、あとそれを90度回転したベクトルを準備しておけば、適宜それらをa,b,c,dに準じた長さにして(PX,PY)に足しこむだけ。

int PX,PY,VX,VY;
int A,B,C,D;

void go(double a,double b) {
	_P("%.12lf %.12lf\n",PX+a,PY+b);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>PX>>PY>>VX>>VY;
	cin>>A>>B>>C>>D;
	
	double vv=sqrt(VX*VX+VY*VY);
	double vx=VX/vv;
	double vy=VY/vv;
	double lx=-vy;
	double ly=vx;
	double rx=-lx;
	double ry=-ly;
	
	go(vx*B,vy*B);
	go(lx*A/2,ly*A/2);
	go(lx*C/2,ly*C/2);
	go(lx*C/2-vx*D,ly*C/2-vy*D);
	go(rx*C/2-vx*D,ry*C/2-vy*D);
	go(rx*C/2,ry*C/2);
	go(rx*A/2,ry*A/2);
}

P. Area of a Star

図中円周上の頂点を上から時計回りに1,2,...,nとする。
辺1-(1+n/2)と2-(3+n/2)の交点をAとする。三角形OA1の面積が求められればその2n倍が解となる。
∠O1Aはπ/2n、∠1OAはπ/nである。
辺O1の長さがrなので、三角形OA1の1辺と2角がわかっており、あとはその面積は
三角形の1辺と両端の角|面積の計算|計算サイト
の公式で求められる。

void solve() {
	ll P,R;
	
	double pi=atan(1)*4;
	double ta=pi/P/2;
	double ca=2*pi/P/2;
	double S=sin(ta)*sin(ca)/(2*sin(ta+ca));
	
	double A=S*2*P;
	
	
	_P("%.12lf\n",A*R*R);
}

Q. Pyramids

1辺の長さ1の各図形の体積がわかれば、体積が辺の長さの3乗に比例することを用いて容易に解を得られる。
それぞれ公式などをネットで探して使っても良いし、三角関数を使って底面の正多角形の面積・中心から各頂点への距離を求め、そこからさらに垂体の高さを求めて計算しても良い。

double v3(){
	return sqrt(2)/12;
}
double v4(){
	return 1*1*sqrt(2)/2/3;
}
double v5(){
	double pi=atan(1)*4;
	double a = sqrt(25+10*sqrt(5))/4;
	double r=0.5/sin(pi/5);
	double h=sqrt(1-r*r);
	return a*h/3;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>i>>j>>k;
	_P("%.12lf\n",i*i*i*v3()+j*j*j*v4()+k*k*k*v5());
}

R. Game

nの偶奇がそのまま勝者と一致する。

void solve() {
	ll N;
	cin>>N;
	if(N%2) cout<<1<<endl;
	else cout<<2<<endl;
}

まとめ

おつかれさまでした。
・・・半分はEの読解の疲れだったんだけどね。