bzoj 4206 最大团几何+lis

最大团

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

HINT

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

 1 #include<cstring>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<cmath>
 6 #include<queue>
 7 #include<map>
 8 
 9 #define N 2007
10 #define pi acos(-1)
11 #define inf 1000000007
12 using namespace std;
13 inline int read()
14 {
15     int x=0,f=1;char ch=getchar();
16     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
17     while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 
21 int n,tot,st[N];
22 double r;
23 struct Node
24 {
25     double l,r;
26     Node()
27     {
28         l=r=0;
29     }
30     friend bool operator<(Node x,Node y)
31     {
32         return x.l<y.l;
33     }
34 }a[N];
35 
36 int getlis(int x)
37 {
38     st[tot=1]=x,a[0].r=-inf;
39     for (int i=x+1;i<=n&&a[i].l<a[x].r;i++)
40         if (a[i].r>a[st[tot]].r) st[++tot]=i;
41         else
42         {
43             int l=0,r=tot,ans=tot;
44             while(l<=r)
45             {
46                 int mid=(l+r)>>1;
47                 if (a[st[mid]].r>=a[i].r) ans=min(mid,ans),r=mid-1;
48                 else l=mid+1;
49             }
50             if (ans==1) continue;
51             if (a[i].r<a[st[ans]].r) st[ans]=i;
52         }
53     return tot;
54 }
55 double get_dis(double x,double y)
56 {
57     return sqrt(x*x+y*y);
58 }
59 int main()
60 {
61     n=read(),r=read();
62     for (int i=1;i<=n;i++)
63     {
64         double x=read(),y=read();
65         if (get_dis(x,y)<r){i--,n--;continue;}
66         a[i].l=atan2(y,x)-acos(r/get_dis(x,y));
67         a[i].r=atan2(y,x)+acos(r/get_dis(x,y));
68         if (a[i].r>pi) a[i].r-=2*pi,swap(a[i].l,a[i].r);
69         if (a[i].l<-pi) a[i].l+=2*pi,swap(a[i].l,a[i].r);
70     }
71     sort(a+1,a+n+1);
72     
73     int ans=0;
74     for (int i=1;i<=n;i++)
75         ans=max(ans,getlis(i));
76     printf("%d
",ans);
77 }

bzoj 4206 最大团 几何+lis