首页 > ACM题库 > HDU-杭电 > hdu 4562-守护雅典娜-计算几何-[解题报告]hoj
2015
07-25

hdu 4562-守护雅典娜-计算几何-[解题报告]hoj

守护雅典娜

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 385    Accepted Submission(s): 104



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
 


Source
 

题意:天朝文字不解释

题解:明显可以阻挡怪物的墙有2种情况,一是圆圈围住怪物而雅典娜在外面,二是圆圈围住雅典娜而怪物在外面,所以可以将墙分为2种,然后关键的是将墙的半径按升序排序,那么就不需要在加一个墙的时候和之前所有墙作一次判断了,然后分别对2种墙进行dp,这满足dp的性质,然后合起来再dp一次就可以得出结果了

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
struct point{
    double x,y;
}monster,athena;
struct circle{
    struct point a;
    double r;
}cy[1005],cm[1005];
int dpy[1005],dpm[1005];
int MAX(int x,int y){ return x>y?x:y; }
double dis(struct point p1,struct point p2)
{
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
int cmp(const void *a,const void *b)
{
    struct circle c=*(struct circle *)a;
    struct circle d=*(struct circle *)b;
    return c.r<d.r?-1:1;
}
int check(struct circle c1,struct circle c2)
{
    double temp=dis(c1.a,c2.a);
    return temp<c1.r-c2.r||temp>c1.r+c2.r;
}
int main()
{
    int i,j,t,n,flag1,flag2;
    int ally,allm,cas=1,res;

    //freopen("t.txt","r",stdin);
    scanf("%d",&t);
    athena.x=athena.y=0;
    while(t--)
    {
        scanf("%d%lf%lf",&n,&monster.x,&monster.y);
        for(ally=allm=i=0;i<n;i++)
        {
            scanf("%lf%lf%lf",&cy[ally].a.x,&cy[ally].a.y,&cy[ally].r);
            flag1=dis(cy[ally].a,monster)<cy[ally].r;
            flag2=dis(cy[ally].a,athena)<cy[ally].r;
            if(!flag1&&flag2) ally++;
            else if(flag1&&!flag2) cm[allm++]=cy[ally];
        }
        qsort(cy,ally,sizeof(cy[0]),cmp);
        qsort(cm,allm,sizeof(cm[0]),cmp);
        for(res=i=0;i<ally;i++)
        {
            for(dpy[i]=1,j=0;j<i;j++)
            {
                if(check(cy[i],cy[j]))
                    dpy[i]=MAX(dpy[i],dpy[j]+1);
            }
            res=MAX(res,dpy[i]);
        }
        for(i=0;i<allm;i++)
        {
            for(dpm[i]=1,j=0;j<i;j++)
            {
                if(check(cm[i],cm[j]))
                    dpm[i]=MAX(dpm[i],dpm[j]+1);
            }
            res=MAX(res,dpm[i]);
        }
        for(i=0;i<ally;i++)
        {
            for(j=0;j<allm;j++)
            {
                if(check(cy[i],cm[j]))
                    res=MAX(res,dpy[i]+dpm[j]);
            }
        }
        printf("Case %d: %d\n",cas++,res);
    }

    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。