Instantly share code, notes, and snippets.

# ctylim/JAG2016E.cpp Created Apr 24, 2016

What would you like to do?
JAG 2016 E
 #include #include #include #include #include #include #include #include #include #include #include #include #include #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 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 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 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> polys(N); vector voters(M); rep(i, N){ int L; // 頂点数: 15 cin >> L; polys[i] = vector(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 p1, p2; for (vector 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 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 poly: polys){ isVisible &= !isPierced(poly, c, voter); } cnt += isVisible ? 1 : 0; } ret = max(ret, cnt); } } output(ret, 0); return 0; }