kmjp's blog

競技プログラミング参加記です

yukicoder : No.461 三角形はいくつ？

yukicoder

ちょっとゴリ押し感あるけども。
http://yukicoder.me/problems/no/461

問題

正三角形の内部にN本の辺に平行な線分を追加する。
各線分の位置は与えられており、各線分は頂点の１つP[i]と、比率A[i],B[i]で与えられる。
各線分は、指定された頂点P[i]と、他の２頂点を結ぶ２辺をそれぞれA[i]:B[i]で分割した頂点同士を結んだ線となる。

こうして作った正三角形および内部の線分で構成される正三角形はいくつあるか。

解法

各線分のパラメータについて、A[i]:B[i]と比率表記だと分かりにくいのでR[i]=A[i]/(A[i]+B[i])と割合で考える。
線分はP[i]ごとに分類し、R[i]で昇順ソートしておこう。

  • ３本とも元の正三角形の辺で構成される正三角形：１通り
  • 元の正三角形の２辺と、追加した線分で構成される正三角形：Ｎ通り
  • 元の正三角形の２辺と、追加した線分で構成される正三角形
    • 平行でない２つの線分の組み合わせ(i,j)を考える。R[i]+R[j]＞1であればそのような正三角形が作れる。
  • 追加した線分で構成される正三角形
    • 平行でない３つの線分の組み合わせ(i,j,k)を考える。総当たりするとO(N^3)かかりTLEするので、i,jを総当たりし、kが何通りあるか考える。
    • まず前提としてi,jの２つの線分が交差するよう、R[i]+R[j]＞1であるものとする。
    • R[k]が1-min(R[i],R[j])＜R[k]＜2-(R[i]+R[j])を満たす場合、３線分は逆三角形をなす。
    • R[k]が2-(R[i]+R[j])＜R[k]を満たす場合、３線分は正三角形をなす。
    • よって上２つを合わせて、1-min(R[i],R[j])＜R[k]となるkをlower_boundなどで一気に数え上げよう。ただしR[k]=2-(R[i]+R[j])となるkは取り除く(この場合３線分が１点で交わり正三角形を成さない)

R[i]を小数で処理する場合、O(10^-16)程度の精度を持つ必要があり、long doubleでなければ通らない。
有理数クラスを持つならそちらの方が確実だろう。

int N;
int P[404040],A[404040],B[404040];
vector<long double> V[3];
ll ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	long double eps=1e-18;
	
	cin>>N;
	FOR(i,N) {
		cin>>P[i]>>A[i]>>B[i];
		V[P[i]].push_back((long double)1.0*A[i]/(A[i]+B[i]));
	}
	FOR(i,3) sort(ALL(V[i]));
	ll ret=N+1;
	FORR(r,V[0]) {
		FORR(r2,V[1]) if(r+r2>1+eps) ret++;
		FORR(r2,V[2]) if(r+r2>1+eps) ret++;
	}
	FORR(r,V[1]) {
		FORR(r2,V[2]) if(r+r2>1+eps) ret++;
	}
	FORR(r,V[0]) FORR(r2,V[1]) {
		if(r+r2<1-eps) continue;
		long double hoge=1-min(r,r2);
		ret += V[2].end()-lower_bound(ALL(V[2]),hoge-eps);
		hoge=2-(r+r2);
		ret-=lower_bound(ALL(V[2]),hoge+eps)-lower_bound(ALL(V[2]),hoge-eps);
	}
	cout<<ret<<endl;
	
}

まとめ

本番doubleじゃ通らずlong doubleでゴリ押した。有理数クラス使った方がよかったかな…。