JAG Contest 2016 Domestic E - 選挙活動

jag2016-domestic.contest.atcoder.jp

問題文

省略

解法(反転して表示)

オーソドックスな幾何． 列挙して意味のある候補点を列挙する．この候補点に意味のない点が含まれていてもいいので雑に． 候補点を列挙するために，有権者から各多角形の頂点への直線を伸ばして，それを列挙してみる(見える範囲が変化する角度に対する線分を考えるとそれを列挙するのが合理的そうなことが分かる)． で，得られた直線全てについて，2つの直線の交点を求めて，それを候補点とする．

候補点が求まれば，各点について，それを見ることのできる有権者の数を数えれば良い． 条件の「多角形の頂点または有権者のいる場所の座標のうち3点が同一直線状に存在することはない．」がありがたい制約で，これのおかげで幾何パートがかなり楽になっていると言っても良い． 多分実装の軽い方針で多角形と線分の交差判定をする必要があるんですが，その制約のおかげで以下のような図のケースを考えなくて良いため，楽になる．

計算量はよく見積もってないけど多項式時間で終わるしそんなに大きくない．

ソース

#include <bits/stdc++.h>
using namespace std;
 
const double EPS = 1e-8;
const double INF = 1e12;
typedef complex<double> P;
typedef vector<P> G;
namespace std {
  bool operator < (const P& a, const P& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
 
double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}
 
double dot(const P& a, const P& b) {
  return real(conj(a)*b);
}
struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};
 
int ccw(P a, P b, P c) {
  b -= a; c -= a;
  if (cross(b, c) > 0)   return +1;     
  if (cross(b, c) < 0)   return -1;      
  if (dot(b, c) < 0)     return +2;       
  if (norm(b) < norm(c)) return -2;       
  return 0;
}
 
P crosspoint(const L &l, const L &m) {
  double A = cross(l[1] - l[0], m[1] - m[0]);
  double B = cross(l[1] - l[0], l[1] - m[0]);
  if (abs(A) < EPS && abs(B) < EPS) return m[0]; 
  if (abs(A) < EPS) assert(false); 
  return m[0] + B / A * (m[1] - m[0]);
}
 
// 以下の条件式で，0未満としているのは(ccwの返り値は-EPSなのは全く意味ない)，線分が端点で接しているときは当たっていないことにしたいため．
bool intersectSS(const L &s, const L &t) {
  return ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]) < -EPS &&
         ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]) < -EPS;
}
bool intersectLL(const L &l, const L &m) {
  return abs(cross(l[1]-l[0], m[1]-m[0])) > EPS || 
         abs(cross(l[1]-l[0], m[0]-l[0])) < EPS;   
}
 
 
P in(){
    double x,y;
    cin >> x >> y;
    return P(x,y);
}
int main(){
    int N,M;
    cin >> N >> M;
    vector<L> ls;
    vector<G> gs; 
    vector<P> check;
    vector<P> look;
    for(int i = 0 ; i < N ; i++){
        int L;
        cin >> L;
        G g;
        for(int j = 0 ; j < L ; j++){
            g.push_back(in());
            check.push_back(g.back());
            look.push_back(g.back());
        }
        gs.push_back(g);
    }
    vector<P> people;
    for(int i = 0 ; i < M ; i++){
        people.push_back(in());
    }
    for(int i = 0 ; i < M ; i++){
        for(int j = 0 ; j < check.size() ; j++){
            ls.push_back(L(check[j],people[i]));
        }
    }
    
    for(int i = 0 ; i < ls.size() ; i++){
        for(int j = i + 1 ; j < ls.size() ; j++){
            if( intersectLL(ls[i],ls[j]) ){
                look.push_back(crosspoint(ls[i],ls[j]));
            }
        }
    }
    int ans = 0;
    for( auto lp : look ){
        int sub = 0;
        for(int i = 0 ; i < M ; i++){
            int f = 1;
            for(int j = 0 ; j < gs.size() ; j++){
                for(int k = 0 ; k < gs[j].size() ; k++){
                    L l(gs[j][k],gs[j][(k+1)%gs[j].size()]);
                    if( intersectSS(l,L(people[i],lp)) ) f = 0;
                }       
            }
            if( f ) sub++;
        }
        ans = max(ans,sub);
    }
    cout << ans << endl;
}