SRM 271 Div 1 Hard ConvexHull

問題

座標平面上に縦n横mの長方形がある。
各辺は座標軸に平行で、一つの頂点は原点である。

この長方形の内部（周を含む）に描ける、全ての頂点が格子点上にある凸n角形について。
最大のnはいくつか。

制約条件

n,m≦200

方針

少なくとも4点は長方形の周上にあるとしてよい。
まずは点(0,0)から点(x,y)まで、下に凸な折れ線を引いた時に、
頂点が最大でいくつできるかを各x,yに対してDPで求める。

これは、ありえる全ての角度を列挙して、表を更新していくDPでできる。
角度の列挙は0≦i≦x, 0≦j≦yかつi,jが互いに素であるようなi,jを列挙すればいい。
この角度を、大きい順に並べ、
同じ角度を二度使わないよう、角度を最も外側のループに、
かつx座標を降順にしてDPテーブルを更新する。

折れ線の列挙ができたら、
長方形の左側の辺に取る点Aの高さlおよび長方形の右側に取る点Bの高さをrとして、
点Aから、長方形の下側の辺上の点Cを通り、点Bに辿り着くような折れ線に対して、
頂点がいくつ取れるか、最大値を求める。

これは、上をdp2[l][r]とおけば、（よくよく考えれば別にDPではないのだが）
下の辺に点Cのみが存在する場合は、間の点Cをどこに取るかn+1通り試すだけで求まる。
下の辺に二点が存在する場合、二点間の距離は1が最良であるので、この場合もその二点のとり方をn通り試せば求まる。

最後に、左側の辺上の点をどの位置にし、右側の頂点をどの位置にするかも全部試して決める。

ソースコード

bool cmp(const pi &a,const pi &b){
  return a.second*b.first<b.second*a.first;
}
int dp[201][201], dp2[201][201];

class ConvexHull {
  public:
  int intHull(int m, int n) {
    vector<pi> v;
    for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)if(__gcd(i,j)==1)
      v.pb(mp(i,j));
    sort(all(v),cmp);
    
    memset(dp,0,sizeof(dp));
    memset(dp2,0,sizeof(dp2));
    
    for(int it=(int)v.size()-1;it>=0;it--){
      int dx=v[it].first, dy=v[it].second;
      
      for(int x=m;x>=dx;x--)for(int y=n;y>=dy;y--)
        dp[x][y]=max(dp[x][y],dp[x-dx][y-dy]+1);
    }
    
    //rep(i,m+1)rep(j,n+1)cerr<<dp[i][j]<<(j==n?"\n":" ");
    
    rep(l,m+1)rep(r,m+1)rep(mid,n+1){
      dp2[l][r]=max(dp2[l][r],dp[l][mid]+dp[r][n-mid]);
      if(mid<n)dp2[l][r]=max(dp2[l][r],dp[l][mid]+dp[r][n-mid-1]+1);
    }
    
    int ans=0;
    rep(l,m+1)rep(r,m+1){
      ans=max(ans,dp2[l][r]+dp2[m-l][m-r]);
      if(l<m)ans=max(ans,dp2[l][r]+dp2[m-l-1][m-r]+1);
      if(r<m)ans=max(ans,dp2[l][r]+dp2[m-l][m-r-1]+1);
      if(l<m&&r<m)ans=max(ans,dp2[l][r]+dp2[m-l-1][m-r-1]+2);
    }
    
    return ans;
  }
};