AOJ1175 そして，いくつになった？

解法

---

ふぇぇって考えてるとbitDPに帰着すると思う。
前処理で円と円の交差判定が必要で,
円Oと円O'間の距離が Oの半径 + O'の半径未満だったら交差してないと判定する。
距離はsqrtとらずに整数でやると誤差らずに出来て良かった。

ソース

---

#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair < int , int > Pt;
bool dp[1 << 24];
Pt pts[24];
int n, r[24], c[24];
int hoge[24];
const int INF = 1 << 28;
bool intersect( Pt a, Pt b, int r1, int r2){
  return pow( a.first - b.first, 2) + pow( a.second - b.second, 2) < pow( r1 + r2, 2);
}
 
int rec( int bit){
  if(dp[bit]++) return -INF;
  int ret = 0;
 
  for(int i = 0 ; i < n ; i++ ){
    if((bit >> i) & 1){
      for(int j = i + 1 ; j < n ; j++ ){
        if( (bit >> j) & 1 && c[i] == c[j] && !(bit & hoge[i]) && !(bit & hoge[j])){
          ret = max( ret, rec( bit & ~(1 << i) & ~(1 << j)) + 2);
        }
      }
    }
  }
  return ret;
}
int main()
{
  while(cin >> n, n){
    fill_n( dp, 1 << 24 , false);
    fill_n( hoge, 24 , 0);
 
    for(int i = 0 ; i < n ; i++ ){
      cin >> pts[i].first >> pts[i].second >> r[i] >> c[i];
      for(int j = 0 ; j < i ; j++ ){
        if(intersect(pts[i],pts[j],r[i],r[j])) hoge[i] |= 1 << j;
      }
    }
    cout << rec((1 << n) - 1) << endl;
  }
}