Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
JAG 2016 E
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment