mayoko’s diary

プロコンとかいろいろ。

SRM 562 div1 med CheckerFreeness

問題

TopCoder Statistics - Problem Statement

白い頂点と黒い頂点が与えられる。白い頂点からなる線分と黒い頂点からなる線分で, 交差するものは存在するか。

解法

実は, 線分が交差する場合, 白い頂点の線分か黒い頂点の線分のいずれかはその凸包のいずれかの線分であることが示せます。

片方の凸包がもう片方の凸包を内包している場合
白い頂点の凸包が黒い頂点の凸包の内側にあることにしましょう。
この場合に, 白い頂点の線分と黒い頂点の線分で交差するものがあるのに白い頂点の凸包上のどの線分を使っても黒い頂点の線分と交差しないとします。

すると, 黒い頂点は白い頂点の凸包の外側, かつ黒い頂点の凸包の内側の部分にのみ存在します。この線分と白い頂点の凸包の内側にある白い頂点の線分が交差するので, 必然的に白い頂点の凸包の線分と黒い頂点の線分は交差します。よって矛盾です。

2 つの凸包が交差している場合
これは普通に交差してるのでいいですね。
上記以外の場合
この場合は二つの頂点がある直線で完全に分割されているので線分と線分が交差することはあり得ないです。

ということでこれを正直に実装すれば OK です。座標値が結構大きいので long double 使わないと危ないかもしれません。

typedef long double Real;

Real eps = 1e-12;

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

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

struct P {
    Real x, y;
    P() {}
    P(Real x, Real 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*(Real d) const {return P(x*d, y*d);}
    Real dot(P p) const {return add(x*p.x, y*p.y);} // 内積
    Real det(P p) const {return add(x*p.y, -y*p.x);} // 外積
    Real dist(P p) const {return sqrt((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y));} // 距離
    void normalize() {Real 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;
}
// 線分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));
}

vector<ll> convert(vector<string> X) {
    string s;
    vector<ll> ret;
    for (string t : X) 
        s += t;
    stringstream ss(s);
    ll x;
    while (ss >> x) {
        ret.push_back(x);
    }
    return ret;
}

bool check(vector<P> c, vector<P> o) {
    int k = c.size();
    int m = o.size();
    for (int i = 0; i < k; i++) {
        int ni = (i+1)%k;
        for (int j = 0; j < m; j++) for (int l = j+1; l < m; l++) {
            if (parallel(c[i], c[ni], o[j], o[l])) continue;
            auto p = intersection(c[i], c[ni], o[j], o[l]);
            if (on_seg(c[i], c[ni], p) && on_seg(o[j], o[l], p)) return true;
        }
    }
    return false;
}

class CheckerFreeness {
public:
    string isFree(vector <string> _whiteX, vector <string> _whiteY, vector <string> _blackX, vector <string> _blackY) {
        vector<ll> whiteX = convert(_whiteX), whiteY = convert(_whiteY);
        vector<ll> blackX = convert(_blackX), blackY = convert(_blackY);
        int n = whiteX.size(), m = blackX.size();
        vector<P> white(n), black(m);
        for (int i = 0; i < n; i++) {
            white[i] = P(whiteX[i], whiteY[i]);
        }
        auto wc = convex_hull(white);
        for (int i = 0; i < m; i++) {
            black[i] = P(blackX[i], blackY[i]);
        }
        auto bc = convex_hull(black);
        if (check(wc, black) || check(bc, white)) return "NO";
        return "YES";
    }
};