//一些点一些圆,过圆不能连线,相邻点不能连线,问最多连几条线
//计算几何模板+区间dp
//关键是判断圆和线段是否相交
#include <cstdio>
#include <cmath>
#include <algorithm>
#define N 500
#define ll long long
#define sqr(x) ((x)*(x))
using namespace std;
bool ok[N][N];
ll n,m,r,f[N][N];
struct poi
{
ll x,y;
poi(ll X,ll Y)
{
x=X;y=Y;
}
poi()
{
}
} p[N],q[N];
ll cro(poi a,poi b)
{
return (a.x*b.y-a.y*b.x);
}
ll dot(poi a,poi b)
{
return a.x*b.x+a.y*b.y;
}
poi tr(poi a,poi b)
{
return poi(a.x-b.x,a.y-b.y);
}
double dis(poi a,poi b)
{
return sqrt((double)(sqr(a.x-b.x)+sqr(a.y-b.y)));
}
bool cmp(poi a,poi b)
{
return (a.x<b.x)||(a.x==b.x && a.y<b.y);
}
bool cmp2(poi a,poi b)
{
return cro(tr(a,p[]),tr(b,p[]))>;
}
bool check(poi a,poi b)
{
double C=dis(a,b);
for(int i=;i<=m;i++)
{
double A=dis(q[i],a);
double B=dis(q[i],b);
double COSA=(B*B+C*C-A*A)/(*B*C);
double COSB=(A*A+C*C-B*B)/(*A*C);
if(COSA<1e-||COSB<1e-){
if(A<1.0*r+1e-||B<1.0*r+1e-)return ;
else continue;
}
double SINA=sqrt(-COSA*COSA);
double H=B*SINA;
if(H<1.0*r+1e-)return ;
}
return ;
}
int main()
{
scanf("%d%d%d",&n,&m,&r);
for(int i=;i<=n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
sort(p+,p++n,cmp);
sort(p+,p++n,cmp2);
for(int i=;i<=m;i++)
scanf("%d%d",&q[i].x,&q[i].y);
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
if(i!= || j!=n)
ok[i][j]=check(p[i],p[j]);
for(int len=;len<=n;len++)
for(int start=;start<=n;start++){
ll end=start+len;
for(int k=start+;k<min(end,n);k++)
f[start][end]=max(f[start][end],f[start][k]+f[k][end]);
f[start][end]+=ok[start][end];
}
printf("%d\n",f[][n]);
}

最新文章

  1. bmob
  2. php错误以及常用笔记
  3. Processor Speculative &amp; pipeline
  4. CoffeeScript学习(2)—— 变量
  5. 使用EasyUI设计.net项目的菜单数实例
  6. HDU 1166 敌兵布阵(线段树)
  7. 如何解决innnerText的兼容性问题
  8. 微信JSAPI支付(比较详细) 关于getRrandWCPayRequest:fail_invalid appid 错误
  9. [HMLY]10.iOS中block的基础用法
  10. 201521123067 《Java程序设计》第6周学习总结
  11. 高可用-mysql安装,双主模式+keepalived
  12. jQuery 学习笔记(4)(文本值相关方法、操控CSS方法、位置和尺寸方法)
  13. BZOJ4856 JSOI2016 病毒感染 区间DP
  14. js 下载文件的操作方法
  15. 记录因xen而导致lvs,realserver转发activeconn为0
  16. ImageView和onTouchListener实现,点击查看图片细节
  17. Weblogic申请和配置SSL证书
  18. Java时间间隔问题在Android中的使用
  19. JS-缓冲运动:菜单栏型悬浮框
  20. datatables传参

热门文章

  1. 搭建LoadRunner中的场景(二) 集合点
  2. Ajax动态切换按钮
  3. PS 滤镜— —球面化效果
  4. 「USACO15FEB」「LuoguP3121」审查(黄金)Censoring (Gold)(AC自动机
  5. 「LuoguP2365」 任务安排(dp
  6. Linux的学习思路
  7. javascript关于undefined的判定
  8. &lt;正则吃饺子&gt; :关于微信支付的简单总结说明(一)
  9. 条款29:为&ldquo;异常安全&rdquo;而努力是值得的
  10. Spring入门第十八课