今天hdu的比赛的第一题，凸包+区间dp。
给出n个点m个圆，n<400，m<100，要求找出凸包然后给凸包上的点连线，连线的两个点不能（在凸包上）相邻，连线不能与圆相交或相切，连线不能相交但是可以有公共端点。
首先找出凸包，然后把n*n条边和m个圆算点到直线距离验证一下边是否与圆相交存到e[n][n]里。
然后显然是一个dp，但是我开始看错题目了以为不能有公共端点，能有公共端点的情况考虑一下像一个找三角形的过程，就是区间dp。
区间dp有一点妙的地方是最大区间范围是凸包点数而不用+1，因为连线的两个点不能在凸包上相邻所以这样就能直接得到最大值。
今天疯狂坑队友了，我要是帮着队友查错就能多对一道题了，因为自己菜没有写出来题还连累队友真的真的很抱歉。
代码在下面，也算是复习dp和码一个找凸包板子，这个方法好像叫graham扫描法？
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<stack>
#include<queue>
using namespace std;
const int maxn=;
int n,m,cnt;
int tot;
double r;
struct nod{
double x,y;
}poi[maxn],po[maxn*],ci[maxn];
bool e[maxn][maxn]={};
int f[maxn*][maxn*]={};
bool cmp(nod a,nod b){
double aa=atan2(a.y-po[].y,a.x-po[].x);
double bb=atan2(b.y-po[].y,b.x-po[].x);
if(aa==bb) return a.x<b.x;
return aa<bb;
}
double cro(nod a,nod b,nod c){
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
void getpo(){
int t=;
for( int i=; i<=n; ++i) {
if( poi[i].y < poi[t].y||( poi[i].y == poi[t].y&&poi[i].x < poi[t].x) ) t=i;
}
po[++cnt]=poi[t];swap(poi[t],poi[]);
sort(poi+,poi+n+,cmp);
po[++cnt]=poi[];
for(int i=;i<=n;++i){
//cout<<poi[i].x<<poi[i].y<<endl;
while(cnt>&&cro(po[cnt-],poi[i],po[cnt])>=)--cnt;
po[++cnt]=poi[i];
}
}
int main(){
int T;scanf("%d",&T);
while(T--){
tot=;
cnt=;
memset(e,,sizeof(e));
memset(f,,sizeof(f));
scanf("%d%d%lf",&n,&m,&r);
for( int i=; i<=n; ++i) scanf("%lf%lf",&poi[i].x,&poi[i].y);
for( int i=; i<=m; ++i) scanf("%lf%lf",&ci[i].x,&ci[i].y);
getpo();//cout<<1111111<<endl;
for(int i=;i<=cnt;++i){
// cout<<po[i].x<<po[i].y<<endl;
for(int j=i+;j<=cnt;++j){
if(i==&&j==cnt)continue;
double a=po[i].y-po[j].y,b=po[j].x-po[i].x;
double c=-(a*po[i].x+b*po[i].y);
e[i][j]=;
e[j][i]=;
for(int w=;w<=m;++w){
double ju=a*ci[w].x+b*ci[w].y+c;
if(ju<)ju=-ju;
ju/=sqrt(a*a+b*b);
if(ju>r)continue;
e[i][j]=;
e[j][i]=;
}
//cout<<i<<j<<e[i][j]<<endl;
}
}
int ans=;
for(int k=;k<=cnt;++k){
for(int i=,j=k;j<cnt*;++i,++j){
for(int t=i;t<=j;++t){
f[i][j]=max(f[i][j],f[i][t]);
if(e[(t-)%cnt+][(j-)%cnt+])f[i][j]=max(f[i][j],f[i][t]+);
}
}
}
for(int i=;i<=cnt;++i)ans=max(ans,f[i][i+cnt-]);
printf("%d\n",ans);
}
return ;
}