自动搬运

查看原文

来自洛谷，原作者为

	Iscream2001 **

搬运于2025-08-24 21:43:29，当前版本为作者最后更新于2018-02-28 10:34:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先O（n^4）的dp显然。。 但是n<=250跑不过。。。

考虑换一种方式dp。。。

观察凸包发现从一个点开始，向某一方向沿着边走一圈，边的斜率都是单调的。。。

于是考虑把所有边都连出来，然后按照极角序排序，然后枚举凸包起点dp。。因为保证了边的极角序单调，也就保证了dp顺序的正确性。。

效率是O（n^3），就可以通过此题了

最后是代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
#define N 270
#define mod 100000000
#define ept 1e-12
#define LL long long
#define pa pair<int,int>
using namespace std;
int n,cnt,ans;
int f[N];
struct P{
	int l,r;
	double x,y;
}p[N],e[N*N];
bool cmp(P a,P b){
	return atan2(a.x,a.y)<atan2(b.x,b.y);
}
int main(){
	cnt=ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lf%lf",&p[i].x,&p[i].y);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if(i==j) continue;
			e[++cnt].l=i;e[cnt].r=j;
			e[cnt].x=p[j].x-p[i].x;
			e[cnt].y=p[j].y-p[i].y;
		}
	sort(e+1,e+1+cnt,cmp);
	for(int i=1;i<=n;i++){
		memset(f,-62,sizeof(f));
		f[i]=0;
		for(int j=1;j<=cnt;j++)
			f[e[j].r]=max(f[e[j].r],f[e[j].l]+1);
		ans=max(ans,f[i]);
	}
	printf("%d\n",ans);
	return 0;
}