TTPC2015 H 包囲

2015/10/05 (Mon) AtCoder TTPC 幾何

問題

日本語

方針

答えとしてあり得る多角形は三角形か四角形しかない． なぜなら，答えの多角形を適当に三角形に分解したとき，境界線上に原点があるなら，その両側の三角形からなる四角形以外は不要． そうでない場合は原点を含む三角形以外は不要．

答えが三角形のとき $O(n^3)$ なので普通に全探索できる． 四角形の場合は，必ず対角線上が原点を含んでいる．なので原点を通るような線分に対して，それを底辺とするような三角形を両側に取ってきて最小値を更新していく．

long long を使わないとオーバーフローする．

実装

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define range(i,a,b) for(ll i=a; i<ll(b); i++)
#define rep(i,b) range(i,0,b)
int const inf = numeric_limits<int>::max()/8;

int n, x[300], y[300];
int origin[300][300], area2[300][300][300], contain[300][300][300];

double solve(){
    if(n < 3) return -1;
    rep(i,n)rep(j,n){
        origin[i][j] = x[i]*y[j] - x[j]*y[i] == 0 && x[i]*x[j] < 0;
        rep(k,n){
            int p = x[i]*y[j] - x[j]*y[i];
            int q = x[j]*y[k] - x[k]*y[j];
            int r = x[k]*y[i] - x[i]*y[k];
            area2[i][j][k] = p + q + r;
            contain[i][j][k] = (p > 0 && q > 0 && r > 0) || (p < 0 && q < 0 && r < 0);
        }
    }
    int ans2 = inf;
    rep(i,n)rep(j,i){
        if(origin[i][j]){
            int min_[3] = {inf,inf,inf};
            int *mini = min_+1;
            rep(k,n){
                int s = area2[i][j][k];
                int sign = (s > 0) - (s < 0);
                if(sign == 0) continue;
                mini[sign] = min(mini[sign], abs(s));
            }
            ans2 = min(ans2, mini[-1]+mini[1]);
        } else {
            rep(k,n){
                if(origin[i][k] || origin[j][k] || origin[k][i] || !contain[i][j][k]) continue;
                ans2 = min(ans2, abs(area2[i][j][k]));
            }
        }
    }
    return ans2 == inf ? -1 : ans2/2.0;
}

signed main(){
    while(cin >> n){
        rep(i,n) cin >> x[i] >> y[i];
        double ans = solve();
        if(ans == -1) puts("Impossible");
        else puts("Possible"), printf("%lf\n", ans);
    }
}