Codeforces #230 Div1 A. Blocked Points

CF#230はABをそこそこの時間で解いた。
Cの正答者が少なかったため、2問でいい順位に入れたのだが残念ながらディスク故障で無効…。
http://codeforces.com/contest/392/problem/A

問題

2次元座標上の格子点において、以下のいずれかの条件を満たす格子点の対A,Bは連結されているとみなす。

• A,Bの距離が1で、どちらの点もブロックされていない
• A,Cが連結されており、B,Cが連結されているような点Cがある。

ここで、原点から距離N内の格子点を特別な点とする。
特別な点が特別でない点と連結されないよう、いくつかの点をブロックしたい。
ブロックする最少の点の数を答えよ。

解法

半径Nの円周に相当する格子点の数を数えればよい。
以下は円の1/4を図示したもので、以下の#部分をカウントするだけ。
O(N)で処理できる。

#
*##
***#
****#
*****#
*****#
*****#
O*****#

ll N;

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	ll tot=0,xx;
	x=0;
	tot=1;
	
	if(N==0) return _P("1\n");
	
	for(xx=N-1;xx>0;xx--) {
		y=sqrt(N*N-xx*xx);
		if(y==x) tot++;
		else tot+=y-x;
		x=y;
	}
	tot*=4;
	cout << tot << endl;
}

まとめ

問題文がわかりにくい…。