JAG Contest 2016 Domestic E - 選挙活動

問題

jag2016-domestic.contest.atcoder.jp

解法

候補になる直線は, 有権者と障害物の頂点を結んだ直線ですが, これを何本も引くことを考えると結局考えるべき頂点は「有権者と障害物の頂点を結んだ直線」同士の交点であることがわかります。

この点を列挙してそれぞれの点で何人の有権者から見えるかを調べれば良いです。

調べるときは, 有権者と X 氏を結ぶ線分に多角形がないかを調べれば良いですが, これはいくつかの線分との交差判定と同じになります。

typedef long double Real;

Real eps = 1e-10;

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

// 線分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;
    Real c1 = ab.det(bp);
    Real c2 = bc.det(cp);
    Real c3 = ca.det(ap);
    if (c1 > 0 && c2 > 0 && c3 > 0) return true;
    if (c1 < 0 && c2 < 0 && c3 < 0) return true;
    return false;
}

vector<P> polygon[10];
P ps[10];
int N, M;

// p-q まで多角形とぶつからずにいけるか
bool check(const P& p, const P& q) {
    for (int i = 0; i < N; i++) {
        int L = polygon[i].size();
        for (int j = 0; j < L; j++) {
            int nj = (j+1)%L;
            if (parallel(p, q, polygon[i][j], polygon[i][nj])) continue;
            P r = intersection(p, q, polygon[i][j], polygon[i][nj]);
            if (on_seg(p, q, r) && on_seg(polygon[i][j], polygon[i][nj], r)) return false;
        }
    }
    return true;
}

// p がいずれかの多角形の内部に存在するか
bool isIn(const P& p) {
    for (int i = 0; i < N; i++) {
        int L = polygon[i].size();
        for (int j = 0; j < L; j++) {
            int nj = (j+1)%L, nnj = (j+2)%L;
            if (inTri(p, polygon[i][j], polygon[i][nj], polygon[i][nnj])) return true;
            if (on_seg(polygon[i][j], polygon[i][nnj], p) && L > 3) return true;
        }
    }
    return false;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        int L;
        cin >> L;
        polygon[i].resize(L);
        for (int j = 0; j < L; j++) cin >> polygon[i][j].x >> polygon[i][j].y;
    }
    for (int i = 0; i < M; i++) cin >> ps[i].x >> ps[i].y;
    // 候補になる頂点を列挙
    vector<P> cand;
    for (int i = 0; i < N; i++) for (P p1 : polygon[i]) for (int j = 0; j < M; j++) {
        for (int k = 0; k < N; k++) for (P p2 : polygon[k]) for (int l = 0; l < M; l++) {
            if (parallel(p1, ps[j], p2, ps[l])) continue;
            P r = intersection(p1, ps[j], p2, ps[l]);
            if (!isIn(r)) cand.push_back(r);
        }
    }
    int ans = 1;
    // 候補点から見える点の数を求める
    for (P p : cand) {
        int tmp = 0;
        for (int i = 0; i < M; i++) {
            if (check(p, ps[i])) tmp++;
        }
        ans = max(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}