11665:Chinese Ink

問題文
http://uva.onlinejudge.org/external/116/11665.html

いくつかの多角形(凸とは限らない)を墨で塗りつぶしたときいくつの多角形ができるか求めよ。

点-多角形包含判定。本番はライブラリが間違ってたらしく通せなかった。spaghetti sourceさんを参考になおした。

#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cfloat>
#include<sstream>
#include<string>
#define curr(P, i) P[(i) % P.size()]
#define next(P, i) P[(i+1) % P.size()]
   
using namespace std;
   
double EPS = 1e-10;

double add(double a, double b){
  if(abs(a+b) < EPS * (abs(a)+abs(b)))return 0;
  return a+b;
}
   
struct point{
  double x, y;
  point(){}
  point(double x,double y) : x(x) , y(y){}
   
  point operator + (point p){
    return point(add(x,p.x), add(y,p.y));
  }
   
  point operator - (point p){
    return point(add(x,-p.x), add(y,-p.y));
  }
};
   
double dot(point a, point b) {return (a.x * b.x + a.y * b.y);}
double cross(point a, point b) {return (a.x * b.y - a.y * b.x);}
double norm(point a){return sqrt(a.x*a.x+a.y*a.y);}
   
int is_point_on_line(point a, point b, point c) {
  return cross(b-a, c-a)==0.0 &&
         (dot(b-a, c-a) > -EPS) &&
         (dot(a-b, c-b) > -EPS);
}
   
   
int is_intersected_ls(point a1, point a2, point b1, point b2) {
   
  if(cross(a1-a2,b1-b2)==0){
    return is_point_on_line(a1,a2,b1) || is_point_on_line(a1,a2,b2)
        || is_point_on_line(b1,b2,a1) || is_point_on_line(b1,b2,a2);
  }
  else {
    return ( cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < EPS ) &&
           ( cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) < EPS );
  }
}

int contain(point p,vector<point>pol){
  bool in=false;
  for(int i=0;i<pol.size();i++){
    point a=curr(pol,i)-p,b=next(pol,i)-p;
    if(a.y>b.y)swap(a,b);
    if(a.y<=0 && 0<b.y && cross(a,b)<0)in=!in;
    if(cross(a,b)==0 && dot(a,b)<=0)return 2;
  }
  return in?1:0;
}
   
bool crossPol(vector<point> pol1, vector<point> pol2){
     
  for(int i=0;i<pol1.size();i++)
    if(contain(pol1[i],pol2))return true;
     
  for(int i=0;i<pol2.size();i++)
    if(contain(pol2[i],pol1))return true;
     
  for(int i=0;i<pol1.size();i++)
    for(int j=0;j<pol2.size();j++)
      if(is_intersected_ls(pol1[i],next(pol1,i),pol2[j],next(pol2,j)))return true;
     
  return false;
}
 
vector<point>pol[100];
bool fg[100];
int n;
void rec(int m){
  fg[m]=true;
  for(int i=0;i<n;i++)
    if(!fg[i]&&crossPol(pol[m],pol[i]))rec(i);
}

int main(void){
  
  while(cin >> n,n){
    cin.ignore();
    
    for(int i=0;i<n;i++)pol[i].clear();
    for(int i=0;i<n;i++){
      string str;
      getline(cin,str);
      stringstream ss;
      ss << str;
      int a,b;
      while(ss >> a, ss >> b)
	pol[i].push_back(point(a,b));
    }
    
    int cnt=0;
    fill(fg,fg+100,false);
    for(int i=0;i<n;i++)if(!fg[i])rec(i),cnt++;
    
    cout << cnt << endl;
  }
  return 0;
}