问题 H: Crazy Rabbit
时间限制: 2 Sec 内存限制: 512 MB
提交: 37 解决: 12
[提交][状态][讨论版]
题目描述
兔子们决定在自己的城堡里安排一些士兵进行防守。给出 n 个点的坐标，和城堡里一个圆心在原点的圆形的障碍
，兔子们希望从中选出 k 个兔子，使得它们两两所在的直线都不与圆相交。兔子们希望知道最多能选出多少兔子
输入
第一行两个整数 N 和 R, 表示兔子的个数和圆的半径接下来 N 行，每行两个整数 xi 和 yi ，表示第 i 只兔子
的坐标保证每只兔子都严格在障碍外部，且两两的所在的直线不与圆相切。
对于 100% 的测试数据, 1 <= n <= 2000; 1 <= R, xi, yi <= 5000
输出
输出一行一个整数, 表示最多能选出多少兔子
样例输入
6 3
0 6
-7 -4
-3 -2
7 -5
-2 3
8 -3
样例输出
4
【样例1解释】
选择第 1, 2, 6, 4 只兔子即可。
我开始想到了二分个数。。。貌似check只能2^n…
实际上从一个兔子作圆的两条切线，作为兔子的视线范围，那么就有几个性质。
1.如果两个兔子的视线范围相交，那么这两个兔子的连线就不会接触到圆。
2.如果两个兔子视线范围互相覆盖，那么连线所在的直线过圆。
3.如果不相交，则连线过圆。
这样问题就变成了在圆上选一些区间，让他们互相相交而不包含。
但这样还是很麻烦QAQ，其实还有一个性质，和线段覆盖的是优弧还是劣弧无关。现在把连线过圆的两种情况视为一种，如果当前被全覆盖，那么换成劣弧就成了不相交。怎么换都是连线过圆的情况。同理，如果当前两线段相交而不互相覆盖，说明线段2覆盖了线段1无法覆盖的一段地方，而线段1改成他的补集后，就覆盖了刚才他无法覆盖的一段。
所以现在问题转化成线段上找区间使其相交而不包含。
可以发现所有区间的左端点都在最靠左区间内部，而区间右端点都在之外。所以我们只要给区间按左端点排序，逐个枚举区间，选出满足这个的区间，然后让区间右端点跑最长上升子序列，更新答案即可。
其实把兔子转化成区间的过程用到了计几。
%%%%%达哥。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define N 2005
#define fir first
#define sec second
#define d double
using namespace std;
int read()
{int sum=0,f=1;char x=getchar();while(x<'0'||x>'9'){
if(x=='-')f=-1;x=getchar();}while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}return sum*f;
}
int n,ans,r;
pair<d,d> a[N];
d b[N],c[N],P=acos(-1.0);
int check(int x)
{if(x==0)return 0;int len=0;c[++len]=b[1];for(int i=2;i<=x;i++){if(b[i]>c[len]){c[++len]=b[i];continue;}int l=upper_bound(c+1,c+len+1,b[i])-c;c[l]=b[i];}return len;
}
int main()
{n=read();r=read();for(int i=1,x,y;i<=n;i++){x=read();y=read();d k=sqrt(x*x+y*y),jj=atan2(y,x),Cos=acos(r/k);d l=jj-Cos,r=jj+Cos;while(l<=-P)l+=2.0*P;while(r>P)r-=2.0*P;if(l>r)swap(l,r);a[i]=make_pair(l,r);}sort(a+1,a+n+1);for(int i=1,len;i<=n;i++){len=0;for(int j=i+1;j<=n;j++)if(a[j].fir<=a[i].sec&&a[j].sec>a[i].sec)b[++len]=a[j].sec;ans=max(ans,check(len)+1);}printf("%d\n",ans);
}