[usaco]2008 Dec Largetst Fence最大のフェンス2‖dp

元サイトは多分もう上がらない・・・
平面上のn点からなる頂点数が最も多い凸多角形を求める.n<=250.
凸包の左下角を列挙するたびに(Grahamを参照して凸包を求めるときの左下角)を考慮し、Grahamのように現在の左下角に対して他の点を極角ソートします.dp,dp[i][j]は現在のエッジがiからjの最大点であることを示し,以下のような遷移を得る.

for (int i=1;i<=n;i++)
    if (x!=i) dp[x][i]=1;
for (int i=1;i<=n;i++)
    for (int j=i+1;j<=n;j++)
        for (int k=1;k

これがn^4ですが、どうやって最適化しますか?f[i]がdp[][i]の最大値であることを記録することができ,これにより列挙kのnを省くことができ,n^3アルゴリズムが得られる.列挙kの過程を省くのでcheckはどうしますか?各セグメントを前処理し、セグメントを極角でソートすればいいです.

#include
#include
#include
#define N 300
using namespace std;
int n,q[N],f[N],dp[N][N],num,ans;
struct hhh
{
    int x,y;
    hhh() : x(0),y(0) {}
    hhh(int _x,int _y) : x(_x),y(_y) {}
    hhh operator - (const hhh &b) const
    {
        return hhh(x-b.x,y-b.y);
    }
    int operator * (const hhh &b) const
    {
        return x*b.y-y*b.x;
    }
}a[N];
struct hh
{
    hhh qwq;
    int a,b;
    bool operator < (const hh &b) const
    {
        return qwq*b.qwq<0;
    }
}v[N*N];

int read()
{
    int ans=0,fu=1;
    char j=getchar();
    for (;j'9';j=getchar()) if (j=='-') fu=-1;
    for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';
    return ans*fu;
}

int check(int x)
{
    memset(f,128,sizeof(f));
    memset(dp,0,sizeof(dp));
    f[x]=0;
    int QwQ=0;
    for (int i=1;i<=num;i++)
    {
        dp[v[i].a][v[i].b]=max(dp[v[i].a][v[i].b],f[v[i].a]+1);
        if (v[i].b!=x) f[v[i].b]=max(f[v[i].b],f[v[i].a]+1);
    }
    for (int i=1;i<=n;i++)
        QwQ=max(QwQ,dp[i][x]);
    return QwQ;
}

int main()
{
    freopen("dot.in","r",stdin);
    freopen("dot.out","w",stdout);
    n=read();
    for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (i!=j)
                v[++num].qwq=a[i]-a[j],v[num].a=i,v[num].b=j;
    sort(v+1,v+num+1);
    for (int i=1;i<=n;i++)
        ans=max(ans,check(i));
    printf("%d
",ans);
    return 0;
}