4206: 最大团
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 91 Solved: 36
[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
0 6
-7 -4
-3 -2
7 -5
-2 3
8 -3
Sample Output
4
HINT
对于100%的数据，1≤N≤2000,|xi|,|yi|,R≤5000
Source
分析：
考虑什么样子的两个点确定的直线是合法的...
我们从每个点向圆做两条切线...这两条切线之间有一段弧...如果两个点确定的直线可以选择，当且仅当这两个点对应的弧相交并且不包含...
现在我们把圆切开展成一条线段，我们把弧覆盖这个切点的点的弧取反...并不会影响答案...
现在我们得到了若干区间，我们要找的是包含区间最多的合法序列使得其满足：
$l_1<l_2<l_3<......<l_n<r_1<r_2<r_3<......<r_n$
现在我们枚举第一个区间是什么，这样我们就确定了可选的$l_i$的范围，我们把可选的区间提取出来，按照$l$排序，然后求$r$的最长上升子序列就好了...
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
//by NeighThorn
using namespace std; const int maxn=2000+5;
const double pi=acos(-1.0),inf=1e8; int n,ans,cas;
double r,tmp[maxn],posx[maxn],posy[maxn]; struct M{ double x,y;
int del; inline void init(void){
del=0;
} friend bool operator < (M a,M b){
if(a.del!=b.del) return a.del<b.del;
if(a.x!=b.x) return a.x<b.x;
if(a.y!=b.y) return a.y<b.y;
} }no[maxn]; signed main(void){
scanf("%d%lf",&n,&r);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&posx[i],&posy[i]),no[i].init();
for(int i=1,x,y;i<=n;i++){
double len=sqrt(posx[i]*posx[i]+posy[i]*posy[i]);
if(len<=r){
no[i].del=1;break;
}
double ang1=atan2(posy[i],posx[i]),ang2=acos(r/len);
no[i].x=ang1-ang2;no[i].y=ang1+ang2;
if(no[i].y>pi) no[i].y-=2*pi,swap(no[i].x,no[i].y);
if(no[i].x<-pi) no[i].x+=2*pi,swap(no[i].x,no[i].y);
}
sort(no+1,no+n+1);ans=0;
while(no[n].del==1) n--;
for(int i=1;i<=n;i++){
double x=no[i].x,y=no[i].y;
for(int j=0;j<n;j++) tmp[j]=inf;
for(int j=i+1;j<=n&&no[j].x<y;j++){
if(no[j].y>no[i].y)
*lower_bound(tmp,tmp+n,no[j].y)=no[j].y;
}
ans=max(ans,(int)(lower_bound(tmp,tmp+n,inf)-tmp)+1);
}
printf("%d\n",ans);
return 0;
}
By NeighThorn