TSG LIVE! 4 プログラミングコンテスト : D : Piramid

遅れて参加したのであんまり解けず。
https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-piramid

問題

1辺1の正方形を、辺を共有するように複数つなげて図形を作ったとする。
図形の面積をSとし、ある正方形の頂点を中心とし、全正方形を内包する最小の円の面積をDとする。

有理数P/Qが与えられるので、S/D≧P/Qπとなる最小の正方形数を求めよ。

解法

2次元座標において、原点が円の中心となるようにし、正方形を軸に平行に敷き詰めていくことを考える。
4頂点のうち、原点から最も遠い点について、原点からの距離の近い順に400万個ほどソートして持っておこう。

今n個の正方形を距離の近い順に置いたとき、その正方形の最遠点までの距離がrとする。
S=nで、D=πr^2なので、S/D≧P/QπとなるにはS*Q≧P*r^2になるまで正方形を置いてみるとよい。

ll P,Q;
double T;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>P>>Q;
	
	if(P==0) return _P("0\n");
	vector<double> V;
	for(x=1;x<=1000;x++) {
		for(y=1;y<=1000;y++) {
			V.push_back(1LL*x*x+1LL*y*y);
		}
	}
	sort(ALL(V));
	FOR(i,V.size()) {
		FOR(j,4) {
			if((i*4+j+1)*Q>=P*V[i]) {
				cout<<(i*4+j+1)<<endl;
				return;
			}
		}
	}
	
}

まとめ

これそこまで難しくないけどなんかみんな避けてたね。