﻿HDU 4562 守护雅典娜-Ocrosoft

# 守护雅典娜

Problem Description

Input

[Technical Specification]
1. 1 <= T <= 100
2. 1 <= N <= 1000
3. 1 <= Ri <= 10 000
4. -10 000 <= X, Y, Xi, Yi <= 10 000，坐标不会相同

Output

Sample Input
```
3
1 5 5
1 0 2
1 5 5
1 0 9
3 5 5
1 0 2
4 5 2
2 0 6

```

Sample Output
```
Case 1: 1
Case 2: 0
Case 3: 2

```

Solution

```#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
#define  rep(a,v,b) for(int a=v;a<b;a++)
#define  repe(a,v,b) for(int a=v;a<=b;a++)
typedef long long LL;
const int INF = INT_MAX / 2;
const int MAXN = 300000+ 10;
const int MOD = 1000000009;
int gcd(int a, int b)
{
if (!b)return a;
return gcd(b, a%b);
}
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
/*(◕‿‿◕) 签订契约,成为马猴烧酒吧 (◕‿‿◕)*/
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
using namespace std;
struct Node
{
int x,y,r;
bool operator <(const Node t)
{
return r<t.r;
}
};
int n,x,y;
int judge(Node t)
{
int flag=0;
if((t.x-x)*(t.x-x)+(t.y-y)*(t.y-y)<t.r*t.r)flag=1;
if((t.x-0)*(t.x-0)+(t.y-0)*(t.y-0)<t.r*t.r)
{
if(flag==1)return 0;
else flag=2;
}
return flag;
}
int main()
{
int T;cin>>T;
int cas=0;
while(T--)
{
vector<Node> v1,v2;
int dp1[MAXN],dp2[MAXN];
ms(dp1),ms(dp2);
scanf("%d%d%d",&n,&x,&y);
for(int i=0;i<n;i++)
{
Node t;cin>>t.x>>t.y>>t.r;
if(judge(t)==1)v1.push_back(t);
else if(judge(t)==2)v2.push_back(t);
}
sort(v1.begin(),v1.end());sort(v2.begin(),v2.end());
int ans1=0;
for(int i=0,vs1=v1.size();i<vs1;i++)
{
dp1[i]=1;
for(int j=0;j<i;j++)
{
double dis=(v1[i].x-v1[j].x)*(v1[i].x-v1[j].x)+(v1[i].y-v1[j].y)*(v1[i].y-v1[j].y);//距离
if(dis<(v1[i].r-v1[j].r)*(v1[i].r-v1[j].r))dp1[i]=max(dp1[i],dp1[j]+1);//不相交，可以共存
}
ans1=max(ans1,dp1[i]);
}
int ans2=0;
for(int i=0,vs2=v2.size();i<vs2;i++)
{
dp2[i]=1;
for(int j=0;j<i;j++)
{
double dis=(v2[i].x-v2[j].x)*(v2[i].x-v2[j].x)+(v2[i].y-v2[j].y)*(v2[i].y-v2[j].y);//距离
if(dis<(v2[i].r-v2[j].r)*(v2[i].r-v2[j].r))dp2[i]=max(dp2[i],dp2[j]+1);//不相交，可以共存
}
ans2=max(ans2,dp2[i]);
}
int ans=max(ans1,ans2);
for(int i=0,vs1=v1.size();i<vs1;i++)
{
for(int j=0,vs2=v2.size();j<vs2;j++)
{
double dis=(v1[i].x-v2[j].x)*(v1[i].x-v2[j].x)+(v1[i].y-v2[j].y)*(v1[i].y-v2[j].y);//距离
if(dis>(v1[i].r+v2[j].r)*(v1[i].r+v2[j].r))//不相交，可以共存
ans=max(dp1[i]+dp2[j],ans);
}
}
printf("Case %d: %d\n",++cas,ans);
}
return 0;
}```