| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 540 人关注过本帖
标题:守护雅典娜-杭电4562
取消只看楼主 加入收藏
Magic_July
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:102
专家分:109
注 册:2012-9-25
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:1 
守护雅典娜-杭电4562
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
以下是自己的代码,不知道是不是精度不对
程序代码:
#include<stdio.h>//y=k*x k=y/x -k*x+y=0 A=-k B=1 |-k*xi+yi|/sqrt(k*k+1)
#include<math.h>//bi(-k*xi+yi)/sqrt(k*k+1)<=ri&&xy(X,Y,xi,yi)>ri
float bi(float x)
{
    if(x>0)
    return x;
    else
    return -x;
}
float xy(float x1,float y1,float x2,float y2)
{
    return sqrt(bi(x1-x2)*bi(x1-x2)+bi(y1-y2)*bi(y1-y2));
}
int main()
{
    int T,N,su,i;
    float X,Y,xi,yi,ri,k;
    scanf("%d",&T);
    for(i=1;i<=T;i++)
    {
        scanf("%d%f%f",&N,&X,&Y);
        su=0;
        k=X/Y;//printf("N=%d,X=%f,Y=%f\n",N,X,Y);
        //printf("%f\n",k);
        while(N--)
        {
            scanf("%f%f%f",&xi,&yi,&ri);
            //printf("%f %f %f\n",xi,yi,ri);
            //printf("%f\n",bi(-k*xi+yi)/sqrt(k*k+1));
            if(xy(0,0,xi,yi)<ri&&xy(X,Y,xi,yi)>ri||xy(0,0,xi,yi)>ri&&xy(X,Y,xi,yi))
            su++;
            if(bi(-k*xi+yi)/sqrt(k*k+1)<=ri&&xy(0,0,xi,yi)>ri&&xy(X,Y,xi,yi)>ri)
            su+=2;
            //printf("%d\n",su);
        }
        printf("Case %d: %d\n",i,su);
    }    
    return 0;
}

这是第3个例子的图
图片附件: 游客没有浏览图片的权限,请 登录注册
搜索更多相关主题的帖子: 坐标系 经典的 塔防游戏 雅典娜 阻止怪物 
2013-06-08 21:41
Magic_July
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:102
专家分:109
注 册:2012-9-25
收藏
得分:0 
回复 2楼 czz5242199
这问题有点看不懂......
求指教
2013-06-08 22:38
快速回复:守护雅典娜-杭电4562
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.018837 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved