浙江财经大学
信息管理与工程学院

HDU 4562 守护雅典娜

本文由 Ocrosoft 于 2016-12-02 19:21:28 发表

守护雅典娜

Problem Description
许多塔防游戏都是以经典的“守护雅典娜”为原型的。玩家需要建立各种防御工具来阻止怪物接近我们的女神——雅典娜。
这里,我们可以建造的防御工具只有标准圆形状的防御墙,建立在雅典娜与怪物出生点之间的防御墙数目越多,胜利的希望就越大。这里,将问题简化到一个二维坐标系里,并且假设雅典娜的坐标为原点(0, 0),怪物出生点的坐标为(X, Y)。有N个给定圆心坐标与半径的防御墙可以供玩家选择建立,但要保证所有的圆都不发生相切或相交的情况。注意这些雅典娜位置与怪物出生点位置也不能在墙壁的边缘,即表示防御墙的圆上。点的面积与墙的厚度都很小,可以忽略不计。
记住,在游戏开始之后,怪物可以沿着任何轨迹,选择突破最少的圆形防御墙来到雅典娜的身边,而一个防御墙一旦被突破,它就会失去保护作用。所以,你的方案必须足够优秀。为了守护女神,快去找出最优的建设方案吧!
 

Input
输入第一行为T,表示有T组测试数据。
每组数据以三个整数N,X,Y开始,接下去的N行每行包括三个整数Xi,Yi,Ri,表示一个可以选择的圆心为(Xi, Yi)半径为Ri的防御墙。
[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
有用的圆分两种:1.只包围了雅典娜;2.只包围了怪物出生点。可以先将这两种圆分离出来,其他的圆都没用,不要了。然后分别对于这两种圆,进行DP。对于某一个圆,考虑【它能包含的最多的圆+1(这个圆)】是不是最多的,如果是,说明这个圆要取,如果不是,说明这个圆不取,而是使用之前的某个圆的最优解。
两组的DP解都解出来后,再对这两组解进行DP,得到能够相容的最多的圆数量。

#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;
}

欢迎转载,请保留出处与链接。Ocrosoft » HDU 4562 守护雅典娜

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址