JAG 2016 E

JAG2016E.cpp

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define repd(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template
const double eps = 1.0e-8;
struct point {double x; double y;};

bool isCrossed(point v1, point v2, point p1, point p2){ // 線分の交差判定
    double t1 = (v2.x - v1.x) * (p1.y - v1.y) - (v2.y - v1.y) * (p1.x - v1.x);
    double t2 = (v2.x - v1.x) * (p2.y - v1.y) - (v2.y - v1.y) * (p2.x - v1.x);
    double s1 = (p2.x - p1.x) * (v1.y - p1.y) - (p2.y - p1.y) * (v1.x - p1.x);
    double s2 = (p2.x - p1.x) * (v2.y - p1.y) - (p2.y - p1.y) * (v2.x - p1.x);
    if (t1 * t2 < 0 && s1 * s2 < 0) return true; // 交差している
    else return false;
}

bool isCrossed_(point v1, point v2, point p1, point p2){ // 線分vが直線pと交差しているか
    double s1 = (p2.x - p1.x) * (v1.y - p1.y) - (p2.y - p1.y) * (v1.x - p1.x);
    double s2 = (p2.x - p1.x) * (v2.y - p1.y) - (p2.y - p1.y) * (v2.x - p1.x);
    if (s1 * s2 < 0) return true; // 交差している
    else return false;
}

bool isPierced(vector<point> poly, point p, point q){ // 線分の多角形貫通判定
    bool ret = false;
    rep(i, poly.size()){
        ret |= isCrossed(poly[i], poly[(i + 1) % poly.size()], p, q);
    }
    return ret;
}

bool isPierced_(vector<point> poly, point p, point q){ // 直線の多角形貫通判定
    bool ret = false;
    rep(i, poly.size()){
        ret |= isCrossed_(poly[i], poly[(i + 1) % poly.size()], p, q);
    }
    return ret;
}

bool isParallel(point p1, point p2, point q1, point q2){ // 直線の平行判定
    double ap, bp, aq, bq;
    ap = p2.y - p1.y;
    bp = p1.x - p2.x;
    aq = q2.y - q1.y;
    bq = q1.x - q2.x;
    if (std::abs(ap * bq - aq * bp) < eps) {
        return true;
    }
    else return false;
}
point intersection(point p1, point p2, point q1, point q2){ // 直線p, 直線qの交点
    double ap, bp, cp, aq, bq, cq;
    ap = p2.y - p1.y;
    bp = p1.x - p2.x;
    cp = p1.y * p2.x - p1.x * p2.y;
    aq = q2.y - q1.y;
    bq = q1.x - q2.x;
    cq = q1.y * q2.x - q1.x * q2.y;
    double d = ap * bq - aq * bp;
    double x = -bq * cp / d + bp * cq / d;
    double y = aq * cp / d - ap * cq / d;
    
    return {x, y};
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    int N, M; // 障害物: 5, 有権者: 10
    cin >> N >> M;
    vector<vector<point>> polys(N);
    vector<point> voters(M);
    rep(i, N){
        int L; // 頂点数: 15
        cin >> L;
        polys[i] = vector<point>(L);
        rep(j, L){
            cin >> polys[i][j].x >> polys[i][j].y;
        }
    }
    rep(i, M) cin >> voters[i].x >> voters[i].y;
    
    int ret = 1;
    
    rep(n1, M) rep(n2, M){
        if (n1 == n2) continue;
        vector<point> p1, p2;
        for (vector<point> poly: polys){
            for (point v: poly){
                if (!isPierced_(poly, voters[n1], v)) p1.pb(v);
                if (!isPierced_(poly, voters[n2], v)) p2.pb(v);
            }
        }
        
        vector<point> crs; // 交点の座標
        for (point po1: p1) for (point po2: p2){
            if (!isParallel(voters[n1], po1, voters[n2], po2)) {
                crs.pb(intersection(voters[n1], po1, voters[n2], po2));
            }
        }
        
        for (point c: crs){ // 交点全てに対して有権者が見えるかどうかを判定
            int cnt = 0;
            for (point voter: voters){
                bool isVisible = true;
                for (vector<point> poly: polys){
                    isVisible &= !isPierced(poly, c, voter);
                }
                cnt += isVisible ? 1 : 0;
            }
            ret = max(ret, cnt);
        }
    }
    
    output(ret, 0);
    return 0;
}