#include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i,n) for(int i = 0; i < (int)(n); i++) #define FOR(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i) #define ALLOF(c) (c).begin(), (c).end() // 各種定数. const double INF = 1e100; const double GOLDEN_RATIO = (sqrt(5.0)-1.0)/2.0; // 入力図形の最大頂点数. #define MAX_VERTICES 100 // 点の定義. typedef complex P; typedef complex PI; template inline T outp(const complex& a, const complex& b) { return (conj(a)*b).imag(); } inline P castP(const PI& p) { return P(p.real(), p.imag()); } template istream& operator>>(istream& is, complex& p) { T x, y; is >> x >> y; p = complex(x, y); return is; } // 軸との位置関係を表す型の定義. enum Side { LEFT = 0, AXIS = 1, RIGHT = 2, }; inline Side flip(Side side) { switch(side) { case LEFT: return RIGHT; case RIGHT: return LEFT; case AXIS: return AXIS; } assert(false); } // 三角形 0--p--q の符号付面積. double triangle_area(const P& p, const P& q) { return (conj(p)*q).imag() / 2; } // 直線 p--q のy切片を返す. double intercept(const P& p, const P& q) { return (p.imag()*q.real() - q.imag()*p.real()) / (q-p).real(); } // whole を 軸 x = x0 で切った時の最大多角形を求める. double cut(vector

whole, const double x0, const vector& on_axis) { const int n = whole.size(); // 切断直線をy軸とする. REP(i, n) whole[i] -= P(x0, 0); // 各点の位置関係を決定する. vector side(n); REP(i, n) side[i] = (on_axis[i] ? AXIS : (whole[i].real() < 0 ? LEFT : RIGHT)); #if 0 // ここで座標値にノイズを加えても問題なく走る. REP(i, n) whole[i] += P(rand()%201-100, rand()%201-100); #endif double res = 0; // 左半平面にある多角形だけ処理して,その後図形を反転してもう一度やる. REP(plane, 2) { // 一度辿ったか,全体が右半平面にあるので気にしない. vector seen(n, false); // 軸を右反平面から左半平面に横切る枝の 切片 -> ID なる map. multimap axis_map; // 軸上の点についてのみ意味を持つ,その点で多角形が軸に触れ // カットされないことを示す bool 値. vector touch(n); REP(i, n) { const int h = (i+n-1)%n; const int j = (i+1)%n; if (side[h] == LEFT && side[i] == AXIS && side[j] == LEFT) { // 特殊ケース.h--i--jの位置関係に応じてtouchをセットする. touch[i] = (outp(whole[j]-whole[i], whole[h]-whole[i]) > 0); if (!touch[i]) { // !touch 時には axis_map も必要. const double y = intercept(whole[j], whole[i]); axis_map.insert(make_pair(y, i)); } } else { if (side[i] != LEFT && side[j] == LEFT) { // 右半平面から左半平面に横切る. const double y = intercept(whole[j], whole[i]); axis_map.insert(make_pair(y, i)); } if (side[i] != LEFT && side[j] != LEFT) { // 全体が右半平面にあるので無視する. seen[i] = true; } } } // 各辺を見て辿っていく. // このとき左半平面から始まるものを選ぶ(pの初期設定を楽にするため). REP(s, n) if (!seen[s] && side[s] == LEFT) { // この部分多角形の符号付面積. double area = 0; // 今見ている辺のIDと枝の始点. // 辺がクリップされた場合,pは必ずしもwhole[i]と一致しない. int i = s; P p = whole[s]; while(!seen[i]) { // 元の図形における次の点を調べる. int j = (i+1)%n; P q = whole[j]; // ここで多角形がカットされるか? if (side[j] == LEFT || (side[j] == AXIS && touch[j])) { // ここでは多角形はカットされない. area += triangle_area(p, q); } else { // y切片を求め,枝をクリップする. const double ylo = intercept(whole[i], whole[j]); const P plo = P(0, ylo); // map を引いて,y軸を辿った先の辺を調べる. multimap::iterator it = axis_map.lower_bound(ylo); // not touch ケースで,見つかったエントリが分離する辺をさす場合, // 次のものを採用する. if (side[j] == AXIS && it != axis_map.end() && it->second == j) ++it; // 運悪くendだったら戻す. if (it == axis_map.end()) --it; // これが次の辺.一度使ったエントリは削除する. j = it->second; axis_map.erase(it); // 辿った先の辺のy切片にあたる点を phi とする. const double yhi = intercept(whole[(j+1)%n], whole[j]); const P phi = P(0, yhi); // y軸でクリップされた最初の辺と,辿った分のy軸に対応する // 面積を足す. area += triangle_area(p, plo) + triangle_area(plo, phi); q = phi; } seen[i] = true; i = j; p = q; } // ちゃんとスタート地点に戻ってきたね? assert(i == s); res = max(res, area); } // 全部一度は見たよね? assert(count(ALLOF(seen), false) == 0); // 全部のaxis_mapを使い切った? assert(axis_map.empty()); // 原点について対称になるよう回転してもういっかーい. REP(i, n) { whole[i] *= -1; side[i] = flip(side[i]); } } return res; } inline double golden_division(const double& xlo, const double& xhi) { return GOLDEN_RATIO * xlo + (1-GOLDEN_RATIO) * xhi; } // whole を xlo -- xhi でカットする時の最小値を三分探索. double ternary_search_cut(const vector

& whole, const int iter, const double xlo, const double xhi, const double xmidlo, const double smidlo, const double xmidhi, const double smidhi) { const int n = whole.size(); if (iter <= 0) return min(smidlo, smidhi); return (smidlo < smidhi ? ternary_search_cut(whole, iter-1, xlo, xmidhi, golden_division(xlo, xmidhi), cut(whole, golden_division(xlo, xmidhi), vector(n, false)), xmidlo, smidlo) : ternary_search_cut(whole, iter-1, xmidlo, xhi, xmidhi, smidhi, golden_division(xhi, xmidlo), cut(whole, golden_division(xhi, xmidlo), vector(n, false)))); } // whole を xlo -- xhi でカットするときの最小値を求める. double find_minimum_cut(const vector

& whole, const double xlo, const double xhi) { const int n = whole.size(); const double xmidlo = golden_division(xlo, xhi); const double xmidhi = golden_division(xhi, xlo); const double required_bits = log2(xhi-xlo) + 54; const int required_iter = (int)ceil(required_bits / log2(1+GOLDEN_RATIO)); return ternary_search_cut(whole, required_iter, xlo, xhi, xmidlo, cut(whole, xmidlo, vector(n, false)), xmidhi, cut(whole, xmidhi, vector(n, false))); } // solve! double solve(const vector& original, PI dir) { const int n = original.size(); // 回転ベクトルを求めておく const P rot = P(0, 1) / (castP(dir) / abs(castP(dir))); // 回転した多角形. vector

whole(n); REP(i, n) whole[i] = castP(original[i]) * rot; double res = INF; // まずは特徴点で切ってみる. REP(s, n) { const PI offset = original[s]; vector on_axis(n); REP(i, n) on_axis[i] = (outp(original[i]-offset, dir) == 0); res = min(res, cut(whole, whole[s].real(), on_axis)); } // 特徴点間で切ってみる. vector xs(n); REP(i, n) xs[i] = whole[i].real(); sort(ALLOF(xs)); REP(i, n-1) res = min(res, find_minimum_cut(whole, xs[i], xs[i+1])); return res; } int main(int argc, char** argv) { // メインループ. int n; while(cin >> n && n > 0) { PI dir; cin >> dir; vector original(n); REP(i, n) cin >> original[i]; const double res = solve(original, dir); printf("%.10f\n", res); } return 0; }