TopCoder SRM 558 Div1 Meidum Ear

問題

座標平面の第一象限に青い点がいくつかあり、
x軸の正の部分に赤い点がいくつかある。

これらの点から青い点P, Qおよび、赤い点A, B, C, Dを選び、

• 三角形PADが三角形QBCを厳密に含み
• 角PAD, 角PDA, 角QBC, 角QCBが全て90度より厳密に小さい

とき、これら６点はEarをなすと言う。

Earをなす6点の選び方は何通りあるか、求めよ。

制約条件

赤い点の個数≦300
青い点の個数≦300
1≦それぞれの座標≦1000

方針

問題を長らく勘違いしていて、（APD, BQCも90度未満でないといけないと思っていた）
解けるけど実装が死ぬ問題だと思っていた…

O(n^2)でも解けるが、以下O(n^3)の解法
P, Qを固定して考える。

A, Bの選び方とC, Dの選び方は独立なので、
それぞれの選び方の場合の数を数えて掛け合わせればよい。

A, Bの選び方のほうだけを説明する。（C, Dのほうは左右が逆であとは同じ）
線分PAがQの上側を通るような、最も右のAをjとする。
選ぶBをiとする。
これに対して、Aの選び方は、max(j, i - 1) + 1通り。
iについてループをまわしてナイーブに足せばよい。

ソースコード

int n, m, rx[300], bx[300], by[300];
void parse(vector<string> &s, int *a, int &n){
	n = 0;
	string t;
	rep(i, s.size()) t += s[i];
	stringstream ss(t);
	while(ss >> a[n]) n++;
}

class Ear {
public:
	long long getCount(vector <string> redX, vector <string> blueX, vector <string> blueY) {
		parse(redX, rx, n);
		parse(blueX, bx, m);
		parse(blueY, by, m);
		sort(rx, rx + n);
		
		ll ans = 0;
		rep(p, m) rep(q, m) if(by[p] > by[q]){
			double x = bx[q] - 1.0 * by[q] * (bx[p] - bx[q]) / (by[p] - by[q]);
			
			int a = lower_bound(rx, rx + n, bx[q]) - rx - 1;
			int b = lower_bound(rx, rx + n, bx[q] + 1) - rx;
			int c = lower_bound(rx, rx + n, min(bx[p] * 1.0, x) - EPS) - rx - 1;
			int d = lower_bound(rx, rx + n, max(bx[p] * 1.0, x) + EPS) - rx;
			
			if(a < 0 || b >= n || c < 0 || d >= n) continue;
			
			int l = 0, r = 0;
			for(int i = a; i >= 0; i--) l += min(i - 1, c) + 1;
			for(int i = b; i < n; i++) r += n - max(i + 1, d);
			
			ans += (ll)r * l;
		}
		
		return ans;
	}
};