Codeforces #334 Div1 D. Ruminations on Ruminants

これは思いつかん。
http://codeforces.com/contest/603/problem/D

問題

2次元座標上で、互いに平行でなく、かつ3点以上が1か所で交差しないようなN個の直線が与えられる。
このうち3直線を選んだ時、その3直線で囲まれた三角形の外接円が原点を通るような直線の組の数を求めよ。

解法

シムソンの定理を用いる。
シムソンの定理によると、三角形の外接円から各辺に下した垂線の足は一直線に並ぶ。

この定理をこの問題の条件で考えると、原点が三角形の外接円上にくるものを求めたいので、原点から3直線に垂線を降ろしたとき、その足が一直線にあるような3直線を求めればよい。
そこで、まず原点から各直線に垂線をおろし、その足の座標を求めよう。

あとはその足の座標のうち、3点が一直線になるものを求めればよい。
この手法としては、1点を中心としてそこから他の各頂点の偏角を求め、偏角が180度異なるような頂点対を列挙すればよい。
この処理はmapやsetを使ってO(N^2*logN)、unordered_setでO(N^2)で済む。

なお、今回の問題では垂線の足の座標は以下のサイトの式を見てわかるとおり有理数になる。
Untitled Document

そこで以下のコードでは座標を有理数で保持し、小数を使うことによる誤差を回避している。

pair<ll,ll> getarg(pair<ll,ll> dx,pair<ll,ll> dy) {
	if(dx.first==0) return {0,(dy.first>0)?1:((dy.first<0)?-1:0)};
	if(dy.first==0) return {(dx.first>0)?1:-1,0};
	ll g1=__gcd(abs(dx.first),abs(dy.first));
	ll g2=__gcd(abs(dx.second),abs(dy.second));
	ll dx2=(dx.first/g1)*(dy.second/g2);
	ll dy2=(dy.first/g1)*(dx.second/g2);
	ll g=__gcd(abs(dx2),abs(dy2));
	return {dx2/g,dy2/g};
}

int N;
int A,B,C;
vector<pair<pair<ll,ll>,pair<ll,ll>>> P;
pair<ll,ll> args[2020][2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A>>B>>C;
		P.push_back({make_pair(C*A,A*A+B*B),make_pair(C*B,A*A+B*B)});
	}
	FOR(j,N) FOR(i,j) {
		pair<ll,ll> dx={P[j].first.first*P[i].first.second-P[j].first.second*P[i].first.first,P[i].first.second*P[j].first.second};
		pair<ll,ll> dy={P[j].second.first*P[i].second.second-P[j].second.second*P[i].second.first,P[i].second.second*P[j].second.second};
		args[i][j]=getarg(dx,dy);
		args[j][i]={-args[i][j].first,-args[i][j].second};
	}
	ll ret[3]={};
	FOR(i,N) {
		map<pair<ll,ll>,int> M,M2;
		int num0=0;
		FOR(j,N) if(i!=j) {
			pair<ll,ll> arg = args[i][j];
			if(arg.first==0 && arg.second==0) num0++;
			else {
				if(arg.first>0 || (arg.first==0&&arg.second>0)) M[arg]++;
				else M2[{-arg.first,-arg.second}]++;
			}
		}
		if(M2.size()<M.size()) swap(M,M2);
		FORR(r,M) ret[0] += r.second*M2[r.first];
		ret[1] += num0*(N-1-num0);
		ret[2] += num0*(num0-1)/2;
	}
	cout<<ret[0]+ret[1]/2+ret[2]/6<<endl;
}

まとめ

シムソンの定理さえ知ってれば、あとは典型問題。
でもこんな定理覚えてないよ…。