2008 Ruins

O(N^3)が想定だとずっと信じていたので必死に考えるも解けなかったのですが、どうやら他の人たちがみんなO(N^4)で解いていて時間的にもかなり余裕だという話を聞いたので、O(N^4)でときました。こっちは簡単。
解法としては、このコードでやったのが
左端の点を決めて、それぞれについてatan2したものでソート。ソートしたら
dp[i][j]:さいごにi-jの辺を使ったときの最大の可能な変数
でO(N^3)のDPをしてやればなんとかなります。ちなみにたぶん
dp1[i][j]:さいごにi-jの辺を使い、傾きが単調現象になる本数
dp2[i][j]:さいごにi-jの辺を使い、傾きが単調増加になる本数
見たいな感じにすると凸包のような感じで解けると思います（これもO(N^4)です）。

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int dp[130][130];
pair<int,int> p[130];
struct wolf{
	int x;
	int y;
};
wolf s[130];
inline bool operator<(const wolf &a, const wolf &b){
	return atan2(a.y,a.x)<atan2(b.y,b.x);
}
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d%d",&p[i].first,&p[i].second);
	for(int i=0;i<a;i++){
		p[i].first+=1001;
		p[i].second+=1001;
	}
	std::sort(p,p+a);
	int ret=0;
	for(int i=0;i<a-1;i++){
		for(int j=i;j<a;j++){
			s[j-i].x=p[j].first-p[i].first;
			s[j-i].y=p[j].second-p[i].second;
		}
		s[a-i].x=0;
		s[a-i].y=0;
		std::sort(s+1,s+a-i);
		for(int j=0;j<=a;j++)
			for(int k=0;k<=a;k++)
				dp[j][k]=0;
		int n=a-i+1;
		for(int j=1;j<n;j++)
			dp[0][j]=1;
		for(int j=0;j<n;j++){
			for(int k=j+1;k<n;k++){
			//	printf("%d ",dp[j][k]);
				for(int l=k+1;l<n;l++){
					if((s[l].x-s[k].x)*(s[j].y-s[k].y)+(s[l].y-s[k].y)*(s[k].x-s[j].x)>=0)dp[k][l]=max(dp[k][l],dp[j][k]+1);
				}
			}
			//printf("\n");
		}
		for(int j=0;j<n;j++)
			ret=max(ret,dp[j][n-1]);
	}
	printf("%d\n",ret);
}