東京工業大学プログラミングコンテスト2015 H - 包囲

解けなかったけどこれも良い問題。

問題

ttpc2015.contest.atcoder.jp

解法

実は答えとしてあり得る多角形は三角形か四角形しかありえません。なぜかというと, n 多角形は一般に n-2 個の三角形に分割することが出来ますが, 基本的には三角形内部に原点がある点だけを選べば良いので, 例えば 5 角形の場合は少なくともひとつの三角形を取り除けます。ただちょっと例外として原点が三角形の辺上にある場合は原点を図形内に入れ込むために四角形にする必要があります。

ということで, 考えるべき図形は三角形か四角形だけです。
三角形の場合は頂点を全探索し, また 2 つの頂点を選んだ時点でその 2 つの頂点の辺上に原点がある場合, 辺の上側/下側の頂点を上手く選んで面積を最小にするような四角形を選びます。

double eps = 1e-10;

double add(double a, double b) {
    if (abs(a+b) < eps * (abs(a)+abs(b))) return 0;
    return a+b;
}

bool equal(double a, double b) {
    return add(a, -b) == 0;
}

struct P {
    double x, y;
    P() {}
    P(double x, double y) : x(x), y(y) {}
    P operator+(P p) const {return P(add(x, p.x), add(y, p.y));}
    P operator-(P p) const {return P(add(x, -p.x), add(y, -p.y));}
    P operator*(double d) const {return P(x*d, y*d);}
    double dot(P p) const {return add(x*p.x, y*p.y);} // 内積
    double det(P p) const {return add(x*p.y, -y*p.x);} // 外積
    double dist(P p) const {return sqrt((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y));} // 距離
    void normalize() {double d = sqrt(x*x+y*y); x /= d; y /= d;} // 正規化
    bool operator<(const P& rhs) const {
        if (x != rhs.x) return x < rhs.x;
        return y < rhs.y;
    }
    bool operator==(const P& rhs) const {
        return equal(x, rhs.x) && equal(y, rhs.y);
    }
};

// 線分p1-p2上に点qがあるかを判定する
bool on_seg(P p1, P p2, P q) {
    return (p1-q).det(p2-q) == 0 && (p1-q).dot(p2-q) <= 0;
}

// 直線p1-p2と直線q1-q2が平行かどうかの判定
bool parallel(P p1, P p2, P q1, P q2) {
    P a = p2-p1;
    P b = q2-q1;
    return a.det(b) == 0;
}

// 直線p1-p2と直線q1-q2の交点
P intersection(P p1, P p2, P q1, P q2) {
    return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));
}

// 点 P が三角形の内部に存在するか
bool inTri(P p, P a, P b, P c) {
    P ab = b-a;
    P bc = c-b;
    P ca = a-c;
    P ap = p-a;
    P bp = p-b;
    P cp = p-c;
    double c1 = ab.det(bp);
    double c2 = bc.det(cp);
    double c3 = ca.det(ap);
    if (c1 > 0 && c2 > 0 && c3 > 0) return true;
    if (c1 < 0 && c2 < 0 && c3 < 0) return true;
    return false;
}

// 三角形の面積
double getTriArea(P a, P b, P c) {
    P p = b-a, q = c-a;
    return 0.5*sqrt(p.dot(p)*q.dot(q) - (p.dot(q))*(p.dot(q)));
}

const int MAXN = 222;
P ps[MAXN];

int main() {
    int N;
    cin >> N;
    const P origin(0, 0);
    for (int i = 0; i < N; i++) {
        cin >> ps[i].x >> ps[i].y;
    }
    double ans = 1e15;
    for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) {
        if (on_seg(ps[i], ps[j], origin)) {
            // 四角形の処理
            double minDist[2] = {1e15, 1e15};
            P n = (ps[i]-ps[j]);
            P tmp = n;
            n.x = -tmp.y;
            n.y = tmp.x;
            n.normalize();
            for (int k = 0; k < N; k++) {
                if (k == i || k == j) continue;
                if ((ps[k]-ps[i]).dot(n) > 0) {
                    minDist[0] = min(minDist[0], (ps[k]-ps[i]).dot(n));
                } else if ((ps[k]-ps[i]).dot(n) < 0) {
                    minDist[1] = min(minDist[1], -(ps[k]-ps[i]).dot(n));
                }
            }
            ans = min(ans, 0.5 * ps[i].dist(ps[j]) * (minDist[0]+minDist[1]));
        } else {
            for (int k = 0; k < N; k++) {
                if (k == i || k == j) continue;
                if (inTri(origin, ps[i], ps[j], ps[k])) {
                    ans = min(ans, getTriArea(ps[i], ps[j], ps[k]));
                }
            }
        }
    }
    if (ans >= 1e14) {
        cout << "Impossible" << endl;
    } else {
        cout << "Possible" << endl;
        printf("%.10lf\n", ans);
    }
    return 0;
}