题目
分析
这是道挺有意思的计算几何题……
算法就是：枚举凸包的最左下点B，然后将所有合法的点按相对于B的极角序排序，这样凸包上的点一定是顺序选的。然后记忆化搜索：设状态f(B,p2,p3)代表：最左下点为B，凸包上选的最后一个点为p2，正在测试选不选p3.那么有两种转移：①不选p3，将p3改为p2->p3这条射线沿逆时针旋转卡到的第一个点。②选p3，将p2改为p3，p3改为以p3为起点，方向为p2->p3的射线沿逆时针旋转卡到的第一个点。
这个过程很像是Graham和卷包裹法的某种综合。
“卡到的第一个点”暴力计算是O(N^3)的，那么如果在每次枚举B时都计算一次会是O(N^4)的。不过实际上我们只需要开始计算一下，记忆化搜索中跳过那些不合法的点即可。
ps：我怎么也开始写意识流题解了……身败名裂……
pps：我擦，意识流题解真省事……
代码
#include
#include
#include
#include
#include
using namespace std;
const int SIZEN=310,INF=0x7fffffff/2;
class Point{
public:
int x,y;
Point(int _x=0,int _y=0){
x=_x;
y=_y;
}
};
void print(const Point &p){
cout<<"("<0){
if(t1==0||cross(P[k]-P[i],P[t1]-P[i])>0) t1=k;
}
if(cross(P[j]-P[i],P[k]-P[j])>0){
if(t2==0||cross(P[k]-P[j],P[t2]-P[j])>0) t2=k;
}
}
from_scan[i][j]=t1;
to_scan[i][j]=t2;
}
}
}
bool valid[SIZEN]={0};
int dp[SIZEN][SIZEN];
int del_step(const int &p1,int p2,int p3){//不选p3
int x=from_scan[p2][p3];
while(x&&!(valid[x]&&cross(P[p2]-P[p1],P[x]-P[p1])>0)){
if(x==p3||x==p1) return 0;
x=from_scan[p2][x];
}
if(!x||x==p3||x==p1) return 0;
if(cross(P[p3]-P[p2],P[x]-P[p2])>0) return x;
else return 0;
}
int sel_step(const int &p1,int p2,int p3){//选p3
int x=to_scan[p2][p3];
while(x&&!(valid[x]&&cross(P[p3]-P[p1],P[x]-P[p1])>0)){
if(x==p3||x==p1) return 0;
x=from_scan[p3][x];
}
if(!x||x==p3||x==p1) return 0;
if(cross(P[p3]-P[p2],P[x]-P[p3])) return x;
else return 0;
}
int DFS(const int &p1,int p2,int p3){//凸包起点p1,目前钦定了p2,待探查p3
if(!p2||!p3) return -INF;
//p1它其实是确定的......
if(cross(P[p1]-P[p2],P[p3]-P[p2])>0) return -INF;
int &ans=dp[p2][p3];
if(ans!=-1) return ans;
ans=1;//直接结束凸包
ans=max(ans,DFS(p1,p3,sel_step(p1,p2,p3))+1);
ans=max(ans,DFS(p1,p2,del_step(p1,p2,p3)));
return ans;
}
int calc(int d){
memset(dp,-1,sizeof(dp));
for(int i=1;i<=N;i++) valid[i]=cmp_coor(P[d],P[i]);
valid[0]=false;valid[d]=true;
int ans=0;
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
if(valid[i]&&valid[j]&&cross(P[i]-P[d],P[j]-P[d])>0) ans=max(ans,DFS(d,i,j)+2);
}
}
return ans;
}
void work(void){
int ans=0;
for(int i=1;i<=N;i++) ans=max(ans,calc(i));
printf("%d\n",ans);
}
void read(void){
scanf("%d",&N);
for(int i=1;i<=N;i++) scanf("%d%d",&P[i].x,&P[i].y);
}
int main(){
freopen("fence1.in","r",stdin);
freopen("fence1.out","w",stdout);
read();
prepare();
work();
return 0;
}