square869120Contest #3 : E - 円と三角形 / Circle and Many Triangles

解けてよかった。
http://s8pc-3.contest.atcoder.jp/tasks/s8pc_3_e

問題

半径1の円周上にN個の点が等間隔で存在する。
これらの点から３つ選び、それらを結んでできる三角形はN(N-1)(N-2)/6通りある。
このうち、面積が小さい順にK個目のものの面積を求めよ。

解法

A以下の面積の三角形がK個以上になるような最小のAを求めればそれが解となる。
よってAに対する二分探索を行えばよい。

次に、面積A以下の三角形がいくつになるかを考える。
1点目を固定し、2点目を総当たりすることを考える。
2点決めれば三角形の底辺の長さが決まるので、面積がA以下となるような三角形の高さが計算できる。
よって3点目の組み合わせもまた二分探索をすることで求められる。

ll N,K;
double T[202020];

double AA(int x,int y) {
	return T[x]+T[y-x]+T[N-y];
}

ll num(double A) {
	ll ret=0;
	for(int x=1;x<N;x++) {
		int y=x+(N-x)/2;
		int tx=x;
		if(AA(x,y)<=A) {
			ret += (N-(x+1));
			continue;
		}
		while(y-tx>1) {
			int m=(y+tx)/2;
			if(AA(x,m)<=A) tx=m;
			else y=m;
		}
		ret += (y-1-x)*2;
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	double PI=atan(1)*4;
	
	cin>>N>>K;
	vector<double> D;
	FOR(i,N) T[i]=sin(i*2*PI/N)/2.0;
	
	
	double L=0,R=2;
	FOR(i,100) {
		double M=(L+R)/2;
		if(num(M)*N>=K*3) R=M;
		else L=M;
	}
	_P("%.12lf\n",L);
}

まとめ

最初に下手に部分点取りに行ったせいもあり時間的に手間取った。
解法にはすぐにたどり着いたのにね。