kmjp's blog

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

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

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

問題

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

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

解法

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

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

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でゴリ押した。有理数クラス使った方がよかったかな…。