【BZOJ4660】Crazy Rabbit

Description

兔子们决定在自己的城堡里安排一些士兵进行防守。给出 n 个点的坐标，和城堡里一个圆心在原点的圆形的障碍，兔子们希望从中选出 k 个兔子，使得它们两两所在的直线都不与圆相交。兔子们希望知道最多能选出多少兔子

Input

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

对于 100% 的测试数据, 1 <= n <= 2000; 1 <= R, xi, yi <= 5000

Output

输出一行一个整数, 表示最多能选出多少兔子

Sample Input

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

Sample Output

4
【样例1解释】
选择第 1, 2, 6, 4 只兔子即可。

题解：神题，先%一发达哥的题解：http://www.cnblogs.com/liu-runda/p/6701557.html。

下面只说如何处理区间不包含。先将所有区间按l排序，然后枚举左端点i，将所有li<lj<ri的区间j都拿出来，然后求出这些区间关于r的最长上升子序列即可。最长上升子序列可以采用基于upper_bound的nlogn的做法，详见代码。

烦人的是，这是一个环，在环上比较大小是一件十分捉鸡的事情。。。还是详见代码吧。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#define pi acos(-1.0)

using namespace std;

const int maxn=2010;

struct qj

{

	double l,r;

}p[maxn];

int n,m,ans;

double R;

double q[maxn],sta[maxn];

bool cmp(const qj &a,const qj &b)

{

	return (a.l==b.l)?(a.r<b.r):(a.l<b.l);

}

int LIS()

{

	int top=0,i;

	sta[++top]=q[1];

	for(i=2;i<=m;i++)

	{

		if(q[i]>sta[top])	sta[++top]=q[i];

		else

		{

			int t=upper_bound(sta+1,sta+top+1,q[i])-sta;

			sta[t]=q[i];

		}

	}

	return top;

}

int main()

{

	scanf("%d%lf",&n,&R);

	int i,j;

	for(i=1;i<=n;i++)

	{

		double a,b,c,d;

		scanf("%lf%lf",&a,&b);

		c=atan2(b,a),d=acos(R/sqrt(a*a+b*b));

		p[i].l=c-d,p[i].r=c+d;

		if(p[i].l<=-pi)	p[i].l+=2*pi;

		if(p[i].r>pi)	p[i].r-=2*pi;

		if(p[i].l>p[i].r)	swap(p[i].l,p[i].r);

	}

	sort(p+1,p+n+1,cmp);

	for(i=1;i<=n;i++)

	{

		for(m=0,j=i+1;j<=n;j++)	if(p[j].l<=p[i].r&&p[j].r>p[i].r)	q[++m]=p[j].r;

		ans=max(ans,LIS()+1);

	}

	printf("%d",ans);

	return 0;

}

巴特西

【BZOJ4660】Crazy Rabbit 结论+DP