bzoj 4206: 最大团 （DP+几何）

Description

Input

Output

Sample Input

Sample Output

HINT

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

Source

题解：DP+几何

一个点如果在圆内，那么一定不会入选，所以对于这种点我们直接丢掉，从每个点作圆的切线。

发现对于两个点来说，如果能同时入选，那么他的切线形成的区域一定有交集，例如图中橙点和紫点的位置。

那么我们如何得到两个切点的极角呢？atan2(y,x)±acos(r/get_dis(x,y)) 就是利用相切形成的直角进行计算。然后保证角度在[-pi,pi]内，以较小的极角为第一关键字，较大的为第二关键字。我们选出的点集需要满足

l[1]<l[2]<...<l[n]<r[1]<r[2]<...<r[n] 我们以第一关键字排序，那么就能保证l有序，然后我们枚举起点，从这个点开始到最后一个点为止，从中选择出一个r的最长上升子序列，入选点的必须满足l<r[begin]

然后就可以用O(nlogn)的时间求解LIS问题。用一个栈维护最长上升子序列，如果当前点大于st[top]，那么直接加入；如果小于st[top]，那么我们在栈中二分最小的满足大于等于r[now]的位置，如果栈中的点不上begin，那么我们用当前点替换栈中的结点。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define N 2003#define pi acos(-1)using namespace std;int n,top,st[N];double r;struct data {	double l,r; 	data(double L=0,double R=0) {		l=L,r=R;	}}a[N];double get_dis(double x,double y){	return  sqrt(x*x+y*y);}int cmp(data a,data b){	return a.l<b.l;}int getlis(int s){	top=0; st[++top]=s; a[0].r=-1000000000;	for (int i=s+1;i<=n&&a[i].l<a[s].r;i++) {		if (a[i].r>a[st[top]].r) st[++top]=i;		else {			int l=0; int r=top; int ans=top;			while (l<=r) {				int mid=(l+r)/2;				if (a[st[mid]].r>=a[i].r) ans=min(mid,ans),r=mid-1;				else l=mid+1;			}			if (ans==1) continue;			if (a[i].r<a[st[ans]].r) st[ans]=i;		}	}	return top;}int main(){	freopen("kong.in","r",stdin);	freopen("kong.out","w",stdout);	scanf("%d%lf",&n,&r);	for (int i=1;i<=n;i++) {		double x,y; scanf("%lf%lf",&x,&y);		if (get_dis(x,y)<r) {			i--; n--;			continue;		}	//	cout<<get_dis(x,y)<<endl;		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-=2*pi,swap(a[i].l,a[i].r);		if (a[i].l<-pi) a[i].l+=2*pi,swap(a[i].l,a[i].r);	}	sort(a+1,a+n+1,cmp);	//for (int i=1;i<=n;i++) cout<<a[i].l<<" "<<a[i].r<<endl;	int ans=0;	for (int i=1;i<=n;i++) 	 ans=max(ans,getlis(i));	PRintf("%d/n",ans);}