Croc Champ 2013 - Final : D. Tennis Rackets

これは自力で解けた。
http://codeforces.com/contest/309/problem/D

問題

1辺の長さが(N+1)の正三角形があり、各辺１毎の間隔でN個ずつの穴がある。
これらの穴のうち、三角形の頂点に近いM個は利用できない。

各辺にある穴を１個ずつ選んだ時、その３点が鈍角三角形となるような選び方の数を答えよ。

解法

O(N^2)で愚直に処理すれば間に合う。
まず２次元座標上で、３角形の頂点が(0,0)、(N+1,0)、( (N+1)/2,(N+1)*√3/2)にあるとする。

下辺中の穴Aを(a,0)、左辺中の穴Bを(b/2,b*√3/2)としたとき、Aが鈍角になる場合を列挙する。
そのためにはABを結ぶ線をAを中心に90度回転し、右辺との交点を求める。
するとこの交点のX座標はとなる。右辺で有効な穴はX座標で(N+M+2)/2～(2N-M+1)/2の間に1/2ずつの間隔で配置されているので上記xより右側に何個あるかカウントしていく。

あとは図形の対称性を活かして定数倍の高速化をすればよい。

int N,M;

void solve() {
	int i,j,k,l,r; string s;
	
	ll a,b,x;
	
	cin>>N>>M;
	ll ret=0;
	for(a=M+1;a<=(N+1)/2;a++) {
		ll t=0;
		for(b=M+1;b<N+1-M && b<2*a;b++) {
			x=(2*a*a-a*b+3*N*b+3*b);
			l = N+1+M+1;
			r = 2*(N+1)-(M+1);
			if(x/(a+b)<l) t += r-l+1;
			else if(x/(a+b)<=r) t+=r-(x/(a+b));
		}
		ret += t*(2-(a==(N+1)/2 && N%2));
	}
	
	cout << ret*3 << endl;
}

まとめ

直線の交差判定に√3が出てきて面倒だったが、結果には√は出てこないのですっきり。