AOJ 1254 : Color the Map

問題リンク：Color the Map | Aizu Online Judge

問題概要：
10個以下の国の情報が多角形として与えられる
それらの国に色を塗っていきたいのだが、隣接する国同士は異なる色で塗りたい
同じ国であるならば同じ色で塗らなければならない
最低何色必要か

解法：
特に工夫はせずに再帰で実際に塗っていった
国と国が隣接しているかどうかは、
線分と線分が端点以外で交差している部分があるかどうかで判定した

コード；

struct P
{
  Point p;
  int type;
  P(Point p=Point(),int type=IINF):p(p),type(type){}
  bool operator < (const P& a)const
  {
    if(!(p == a.p))return p < a.p;
    return type < a.type;
  }
};

bool isParallel(Vector a,Vector b)
{
  return equals(cross(a,b),0.0);
}

bool isParallel(Point a1,Point a2,Point b1,Point b2)
{
  return isParallel(a1-a2,b1-b2);
}

bool isParallel(Segment s1,Segment s2)
{
  return equals(cross(s1.p2-s1.p1,s2.p2-s2.p1),0.0);
}

bool intersect(Segment seg1,Segment seg2)
{
  if(!isParallel(seg1,seg2))return false;

  double dist = distanceSS(seg1,seg2);

  if(!equals(dist,0.0))return false;

  vector<P> vec;
  
  vec.push_back(P(seg1.p1,0));
  vec.push_back(P(seg1.p2,0));
  vec.push_back(P(seg2.p1,1));
  vec.push_back(P(seg2.p2,1));
  sort(vec.begin(),vec.end());
  if(vec[1].p == vec[2].p)return false;
  
  return true;

}

vector<int> G[MAX];
int color[MAX],SIZE,ans;

void rec(int upper,int state)
{
  if(upper >= ans)
    {
      return;
    }

  if(state == (1<<SIZE)-1)
    {
      ans = min(ans,upper);
      return;
    }

  int OK = ((1<<SIZE)-1) & (~state);
  while(OK)
    {
      int use = OK & -OK;
      OK -= use;
      int i = (int)log2(use);
      if((state >> i) & 1)continue;

      int x = 0;
      rep(j,G[i].size())
	{
	  if(color[G[i][j]] == -1)continue;
	  x |= (1<<color[G[i][j]]);
	}

      int OK2 = ((1<<(upper+1))-1) & (~x);
      
      while(OK2)
	{
	  int use2 = OK2 & -OK2;
	  OK2 -= use2;
	  int c = log2(use2);
	  int cost = (upper == c);
	  color[i] = c;
	  rec(upper+cost,state|(1<<i));
	  color[i] = -1;

	}
      return;
    }

}

void compute()
{
  ans = IINF;
  rep(i,SIZE)color[i] = -1;
  rec(0,0);
  cout << ans << endl;
}

int main()
{

  int N;
  while(cin >> N,N)
    {
      map<string,int> Index;
      int dex = 0;
      string country[N];
      vector<Point> coor[N];
      int index[N];

      rep(i,N)
	{
	  cin >> country[i];
	  if(Index.find(country[i]) == Index.end())Index[country[i]] = dex++;
	  int x,y;
	  while(cin >> x, x != -1)
	    {
	      cin >> y;
	      coor[i].push_back(Point(x,y));
	    }
	}

      rep(i,N)
	{
	  index[i] = Index[country[i]];
	}
      int n = Index.size();
      rep(i,n)G[i].clear();

      set<ii> used;

      rep(i,N)
	{
	  REP(j,i+1,N)
	    {	 
	      if(index[i] == index[j])continue;
	      if(used.find(ii(index[i],index[j])) != used.end())continue;

	      vector<Point> vec;
	      bool check = false;
	      
	      rep(k,coor[i].size())
		{
		  Segment seg1 = Segment(coor[i][k],coor[i][(k+1)%coor[i].size()]);
		  rep(l,coor[j].size())
		    {
		      Segment seg2 = Segment(coor[j][l],coor[j][(l+1)%coor[j].size()]);

		      if(intersect(seg1,seg2))
			{
			  check = true;
			  goto Skip;
			}
		    }
		}
	    Skip:;	      
	      if(check)
		{
		  used.insert(ii(index[i],index[j]));
		  used.insert(ii(index[j],index[i]));
		  G[index[i]].push_back(index[j]);
		  G[index[j]].push_back(index[i]);
		}
	    }
	}

      SIZE = n;

      compute();

    }
  return 0;
}