3130:How I Mathematician Wonder What You Are!

keyword

平面幾何　C++

概要

頂点数N(<50)の多角形が与えられる。このとき、全ての頂点と自身を結んだ線分が多角形の外部に出ないような点が存在するかどうか判定する問題。
凸多角形の切断を繰り返す。計算量O(N^2)。

int solve(vector<point> ps){
    vector<point> as;
    as.push_back( point(-200000, +200000) );
    as.push_back( point(-200000, -200000) );
    as.push_back( point(+200000, -200000) );
    as.push_back( point(+200000, +200000) );
    int n = ps.size();
    for(int i=0; i<n; i++){
        as = convexCut(as, ps[i], ps[(i+1)%n]);
    }
    return as.empty()?0:1;
}