题意：给出一个点p(X,Y)以及若干圆。从中选出尽可能多的圆满足：圆能且只能包含p或者原点中的一个（不能在圆上）；圆之间不能相交或者相切。
链接：点我
用dp求满足条件包含一个点圆的最多数目，然后两个点再求最大的即可
思路：首先分理出只包含原点或者p的圆，然 后分别按照半径升序排序。分别对包含原点和p的进行dp。f1[i]表示包含原点的圆中前i个最多选出多少个。f2[i]表示p的。然后合并。就是枚举 f1的i和f2的j，若这两个圆不冲突，那么就能选出f1[i]+f2[j]个。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define MOD 1000000007
#define pb(a) push_back(a)
const int INF=0x3f3f3f3f;
const double eps=1e-;
typedef long long ll;
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
const int MAXN=;
int dp1[MAXN],dp2[MAXN];
int n,m,tt,cnt;
struct Node
{
int x,y;
int r;
void in()
{
scanf("%d%d%d",&x,&y,&r);
}
}st,ed,node[MAXN],node1[MAXN],node2[MAXN];
int dis(Node a,Node b)
{
return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(Node a,Node b)
{
return a.r<b.r;
}
int main()
{
int i,j,k;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int ca=;
scanf("%d",&tt);
int X,Y;
st.x=,st.y=;
while(tt--)
{
scanf("%d%d%d",&n,&X,&Y);
ed.x=X,ed.y=Y;
int tot1=,tot2=;
for(i=;i<n;i++)
{
node[i].in();
int d1=dis(st,node[i]);
int d2=dis(ed,node[i]);
if(d1==node[i].r*node[i].r||d2==node[i].r*node[i].r) continue; //点在圆上
if(d1>node[i].r*node[i].r&&d2>node[i].r*node[i].r) continue; //不包含任何点
if((d1<node[i].r*node[i].r)&&(d2<node[i].r*node[i].r)) continue; //两个点都包含
if(d1<node[i].r*node[i].r)
{
node1[tot1++]=node[i];
}
else node2[tot2++]=node[i];
}
cl(dp1);
cl(dp2);
sort(node1,node1+tot1,cmp);
sort(node2,node2+tot2,cmp);
int ans1=,ans2=;
for(i=;i<tot1;i++)
{
dp1[i]=;
for(j=;j<i;j++)
{
if(node1[i].r==node1[j].r) continue;
int d=dis(node1[i],node1[j]);
if(d<(node1[i].r-node1[j].r)*(node1[i].r-node1[j].r))
{
dp1[i]=max(dp1[i],dp1[j]+);
}
}
ans1=max(ans1,dp1[i]);
}
for(i=;i<tot2;i++)
{
dp2[i]=;
for(j=;j<i;j++)
{
if(node2[i].r==node2[j].r) continue;
int d=dis(node2[i],node2[j]);
if(d<(node2[i].r-node2[j].r)*(node2[i].r-node2[j].r))
{
dp2[i]=max(dp2[i],dp2[j]+);
}
}
ans2=max(ans2,dp2[i]);
}
int ans=max(ans1,ans2);
for(i=;i<tot1;i++)
{
for(j=;j<tot2;j++)
{
int d=dis(node1[i],node2[j]);
if(d>(node1[i].r+node2[j].r)*(node1[i].r+node2[j].r))
ans=max(ans,dp1[i]+dp2[j]);
}
}
printf("Case %d: %d\n",ca++,ans);
}
}