TopCoder SRM 382 Div1 Medium PointsOnACircle

問題

円周上の点の集合AとBが似ているとは、
Aを回転移動させてBに重なることをいう。

円周上の点が与えられる。
これらを、青または赤のどちらかに塗りたい（塗らないこともできる）。
塗った後で、青色の点の集合と赤色の点の集合が似ているような塗り方のうち、
塗った点の個数が最大であるものの、塗った点の個数を求めよ。

制約条件

点は原点まわりの角度で指定される。
0度以上360度未満の整数。
点は全て異なる。

方針

移動させる角度を359通り試す。
角度がきまったら、点が対応しうる関係にあるときに、点と点を線で結んだグラフが決まる。

このグラフは、○-○-○のような、
直線がいくつかからなるグラフになる。
このグラフに色を塗る点がいくつ取れる考えてみると、長さLの直線につきL/2組取れることがわかる。

なので、グラフの連結成分の長さを深さ優先探索でそれぞれ見てやればよい。

ソースコード

bool pt[360],v[360];
int rec(int c,int d){
  v[c]=1;
  int res=1, nxt=(c+d)%360, prv=(c-d+360)%360;
  if(pt[nxt]&&!v[nxt])res+=rec(nxt,d);
  if(pt[prv]&&!v[prv])res+=rec(prv,d);
  return res;
}
class PointsOnACircle {
  public:
  int color(vector <string> points) {
    stringstream ss(accumulate(all(points),string()));
    int a,ans=0;
    memset(pt,0,sizeof(pt));
    while(ss>>a)pt[a]=1;
    for(int d=1;d<360;d++){
      memset(v,0,sizeof(v));
      int tmp=0;
      rep(i,360)if(pt[i]&&!v[i])tmp+=rec(i,d)/2*2;
      ans=max(ans,tmp);
    }
    return ans;
  }
};