SRM 486 div1 hard: BatmanAndRobin

問題

TopCoder Statistics - Problem Statement

解法

2 つの交わらない凸多角形が存在するときは, それらの凸多角形の間にそれら２つを分断する直線が存在します。

よって, あり得る直線の候補を列挙して, 分断された直線による凸多角形を求めて, 最小面積を求めれば良いです。

直線の候補がどれくらいあるかを考えてみます。
与えられた n 頂点すべてを通らない直線 L を考えます。これは, n 頂点を 2 つに分断していますが, 一方を A, もう一方を B として, この直線を A, B それぞれに近づけます。直線が初めて A にぶつかった時の頂点を pa, B にぶつかった時の頂点を pb とします。
凸多角形 A のうち, pa を含む辺は 2 つあり, 凸多角形 B のうち, pb を含む辺は同様に 2 つあります。

直線 L は, これらのいずれかの辺と平行になるまで回転させても分断の仕方に影響を与えないので, 直線 L の候補としては, 頂点 vi, vj を結ぶ直線をちょっと半時計回りしたもの, もしくはちょっと時計回りしたもの, だけに限っても問題ありません。

下のコードで, v1, v2, v3, v4 というのを作っていますが, 分断する直線は下図の様に作っています(雑ですみません)。

double eps = 1e-12;

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);
    }
};

// 凸包
vector<P> convex_hull(vector<P> ps) {
    int n = ps.size();
    sort(ps.begin(), ps.end());
    int k = 0;         // 凸包の頂点数
    vector<P> qs(n*2); // 構築中の凸包
    // 下側凸包の作成
    for (int i = 0; i < n; i++) {
        while (k > 1 && (qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1]) <= 0) k--;
        qs[k++] = ps[i];
    }
    // 上側凸包の作成
    for (int i = n-2, t = k; i >= 0; i--) {
        while (k > t && (qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1]) <= 0) k--;
        qs[k++] = ps[i];
    }
    qs.resize(k-1);
    return qs;
}

// 三角形の符号付き面積
double area(P p, P q, P r) {
    return (q-p).det(r-p)/2;
}

// ps からなる凸多角形の面積
double convex_area(vector<P> ps) {
    ps = convex_hull(ps);
    int n = ps.size();
    if (n <= 2) return 0;
    double ans = 0;
    for (int i = 0; i < n; i++) {
        ans += ps[i].det(ps[(i+1)%n]);
    }
    return ans/2;
}

class BatmanAndRobin {
public:
    double minArea(vector <int> x, vector <int> y) {
        int N = x.size();
        vector<P> pnts(N);
        for (int i = 0; i < N; i++) pnts[i] = P(x[i], y[i]);
        double ans = convex_area(pnts);
        for (int i = 0; i < N; i++) for (int j = 0; j < i; j++) {
            vector<int> type(N, -1);
            bool ng = false;
            for (int k = 0; k < N; k++) {
                if ((pnts[j]-pnts[i]).det(pnts[k]-pnts[i]) > 0.1) type[k] = 0;
                else if ((pnts[j]-pnts[i]).det(pnts[k]-pnts[i]) < -0.1) type[k] = 1;
                else if ((pnts[i].dist(pnts[k])) < pnts[j].dist(pnts[k])) type[k] = 2;
                else if ((pnts[i].dist(pnts[k])) > pnts[j].dist(pnts[k])) type[k] = 3;
                else if (i != k && j != k) ng = true;
            }
            if (!ng) {
                vector<P> v1, v2, v3, v4;
                for (int k = 0; k < N; k++) {
                    if (k == i) v1.push_back(pnts[k]);
                    else if (k != i && k != j && (type[k] == 0 || type[k] == 2)) v1.push_back(pnts[k]);
                }
                for (int k = 0; k < N; k++) {
                    if (k == j) v2.push_back(pnts[k]);
                    else if (k != i && k != j && (type[k] == 1 || type[k] == 3)) v2.push_back(pnts[k]);
                }
                for (int k = 0; k < N; k++) {
                    if (k == i) v3.push_back(pnts[k]);
                    else if (k != i && k != j && (type[k] == 1 || type[k] == 2)) v3.push_back(pnts[k]);
                }
                for (int k = 0; k < N; k++) {
                    if (k == j) v4.push_back(pnts[k]);
                    else if (k != i && k != j && (type[k] == 0 || type[k] == 3)) v4.push_back(pnts[k]);
                }
                ans = min(ans, max(convex_area(v1), convex_area(v2)));
                ans = min(ans, max(convex_area(v3), convex_area(v4)));
            }
        }
        return ans;
    }
};