TopCoder SRM 326 Div1 Medium InscribedTriangles

問題

半径5の円がある。
この円周上から三点を、それぞれのx軸から半時計周りに見た角度が区間[angleFrom[i], angleTo[i]]のいずれかに入っているように選ぶ。

このとき、三角形ABCの面積の最大値を求めよ。

制約条件

angleFromとangleToの要素の数は等しい
angleToの要素の数≦30
角度は1/1000度単位で与えられる。

方針

A, B, Cのうち、点Aはどこかの区間の端点であるとして一般性を失わない。
点Bの属する区間を決める。

すると面積に関する三分探索が出来るので、面積を最大にするBを三分探索により求める。
Cは、A, Bを決めると、(A + B) / 2または(A + B) / 2 + 180度に一番近い点が良いので、
候補は2 * 区間の数個程度に絞れる。

最初に重なりのある区間を処理して、全ての区間に重なりがないようにしたが、良く考えるとこの操作は不要……

ソースコード

double a, b;
int n;
vi to, from;

inline double area(double c){
	P A = polar(1.0, a * PI / 180000);
	P B = polar(1.0, b * PI / 180000);
	P C = polar(1.0, c * PI / 180000);
	B -= A; C -= A;
	return abs(B.real() * C.imag() - B.imag() * C.real()) * 12.5;
}
inline double calc(double x){
	b = x;
	double cc = (a + b) / 2;
	double res = 0;
	rep(i, 2){
		rep(j, n){
			if(from[j] <= cc && cc <= to[j]){
				res = max(res, area(cc));
				continue;
			}
			double da = abs(cc - to[j]);
			double db = abs(cc - from[j]);
			
			if(da > 180000) da = 360000 - da;
			if(db > 180000) db = 360000 - db;
			
			if(da < db) res = max(res, area(to[j]));
			else res = max(res, area(from[j]));
		}
		
		cc += 180000;
		if(cc >= 360000) cc -= 360000;
	}
	return res;
}

class InscribedTriangles {
  public:
  double findLargest(vector <int> angleFrom, vector <int> angleTo) {
		
		while(1){
			bool update = 0;
			rep(i, angleTo.size()) rep(j, angleTo.size()) if(i != j){
				if(angleFrom[i] <= angleFrom[j] && angleTo[j] <= angleTo[i]){
					angleFrom.erase(angleFrom.begin() + j);
					angleTo.erase(angleTo.begin() + j);
					goto NEXT;
				}
			}
			rep(i, angleTo.size()) rep(j, angleTo.size()) if(i != j){
				if(angleFrom[j] <= angleTo[i] && angleTo[i] <= angleTo[j]){
					angleTo[i] = angleTo[j];
					angleTo.erase(angleTo.begin() + j);
					angleFrom.erase(angleFrom.begin() + j);
					goto NEXT;
				}
			}
			if(!update) break;
			NEXT:;
		}
		to = angleTo;
		from = angleFrom;

		sort(all(to));
		sort(all(from));
		n = to.size();

		double ans = 0;
		rep(i, n) rep(j, 2){
			a = j ? to[i] : from[i];
			rep(k, n){
				double lo = from[k], hi = to[k], l, r;
				rep(it, 100){
					l = (lo * 2 + hi) / 3;
					r = (lo + hi * 2) / 3;
					if(calc(l) < calc(r)) lo = l;
					else hi = r;
				}
				ans = max(ans, calc(l));
			}
		}
		return ans;
	}
};