最大团

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 142  Solved: 65
[Submit][Status][Discuss]

Description

给出平面上N个点的坐标,和一个半径为R的圆心在原点的圆。对于两个点,它们之间有连边,当且仅当它们的连线与圆不相交。
求此图的最大团。
 

Input

第一行两个整数N和R, 表示点数和圆的半径。
接下来N 行,每行两个整数xi 和yi,表示第i个点的坐标
保证每个点都严格在园外,且两两直线不与圆相切。
 

Output

输出一个整数:最大团的大小。
 

Sample Input

6 3
0 6
-7 -4
-3 -2
7 -5
-2 3
8 -3

Sample Output

4

HINT

对于100%的数据,1≤N≤2000,|xi|,|yi|,R≤5000

 #include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<map> #define N 2007
#define pi acos(-1)
#define inf 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,tot,st[N];
double r;
struct Node
{
double l,r;
Node()
{
l=r=;
}
friend bool operator<(Node x,Node y)
{
return x.l<y.l;
}
}a[N]; int getlis(int x)
{
st[tot=]=x,a[].r=-inf;
for (int i=x+;i<=n&&a[i].l<a[x].r;i++)
if (a[i].r>a[st[tot]].r) st[++tot]=i;
else
{
int l=,r=tot,ans=tot;
while(l<=r)
{
int mid=(l+r)>>;
if (a[st[mid]].r>=a[i].r) ans=min(mid,ans),r=mid-;
else l=mid+;
}
if (ans==) continue;
if (a[i].r<a[st[ans]].r) st[ans]=i;
}
return tot;
}
double get_dis(double x,double y)
{
return sqrt(x*x+y*y);
}
int main()
{
n=read(),r=read();
for (int i=;i<=n;i++)
{
double x=read(),y=read();
if (get_dis(x,y)<r){i--,n--;continue;}
a[i].l=atan2(y,x)-acos(r/get_dis(x,y));
a[i].r=atan2(y,x)+acos(r/get_dis(x,y));
if (a[i].r>pi) a[i].r-=*pi,swap(a[i].l,a[i].r);
if (a[i].l<-pi) a[i].l+=*pi,swap(a[i].l,a[i].r);
}
sort(a+,a+n+); int ans=;
for (int i=;i<=n;i++)
ans=max(ans,getlis(i));
printf("%d\n",ans);
}

最新文章

  1. ubuntu 14.04 ns2.35 ***buffer overflow detected **: ns terminated解决办法
  2. eclipse设置及快捷键
  3. JAVA中的输入方法
  4. startssl,免费的ssl证书申请及注意事项
  5. C++中的RTTI机制解析
  6. B2B多商铺初期权限数据库设计
  7. Redis中常用命令
  8. Android中去掉标题栏的3种方法
  9. WebView Cache 缓存清除
  10. c++primerplus(第六版)编程题&mdash;&mdash;第6章(分支语句和逻辑运算符)
  11. 自定义alert,confirm,prompt事件,模仿window.alert(),confirm(),prompt()
  12. js中的事件,内置对象,正则表达式
  13. WCF Restful调用跨域解决方案
  14. mybatis入门知识
  15. pkg-config 用法
  16. spring cloud实战与思考(五) JWT之携带敏感信息
  17. cobbler自动安装操作系统
  18. IntelliJ IDEA 快捷键说明大全(中英对照、带图示详解)
  19. jupyter命令把.ipynb文件转化为.py文件
  20. Flume学习之路 (三)Flume的配置方式

热门文章

  1. 浪在ACM新春大作战
  2. spring boot 中文乱码问题
  3. JavaScript中childNodes和children的区别
  4. 自测之Lesson11:消息和消息队列
  5. c# dll问题
  6. lintcode-141-x的平方根
  7. Swift 泛型和闭包结合使用
  8. TCP系列29—窗口管理&流控—3、Nagle算法
  9. ios::sync_with_stdio(false)提高C++读写速度
  10. bwapp之xss(blog)