首页 > ACM题库 > HDU-杭电 > HDU 4145-Cover The Enemy-排序-[解题报告]HOJ
2015
04-16

HDU 4145-Cover The Enemy-排序-[解题报告]HOJ

Cover The Enemy

问题描述 :

  Now, the war is coming, no one want to fight with others, but you have to when you are facing.
  As the king of a country, you should defend your country. The condition is that “There are N enemy armies around you, you have two towers and you want to build cannon on each tower to cover all the enemy armies”. The cannon has an “attack distance” R with a cost of R^2.
  You are facing a problem, to cover all the armies and make the cost R1^2 + R2^2 minimal, where R1 and R2 are the attack distance of the two towers.

输入:

The first line contains an integer t, number of test cases, following with t groups of test cases described as following.
For each case, the first line contains four integers: x1, y1, x2, y2, the Coordinates of the two towers.
The next line is an integer n, the number of enemy armies, following with n lines of coordinates: x, y, which is the coordinate of a group of enemy army, where:
  t <= 100
1 <= n <= 100000,
-1000 <= x, y <= 1000
-1000 <= x1, y1, x2, y2 <= 1000

输出:

The first line contains an integer t, number of test cases, following with t groups of test cases described as following.
For each case, the first line contains four integers: x1, y1, x2, y2, the Coordinates of the two towers.
The next line is an integer n, the number of enemy armies, following with n lines of coordinates: x, y, which is the coordinate of a group of enemy army, where:
  t <= 100
1 <= n <= 100000,
-1000 <= x, y <= 1000
-1000 <= x1, y1, x2, y2 <= 1000

样例输入:

2
0 0 10 0
2
-3 3
10 0
0 0 6 0
5
-4 -2
-2 3
4 0
6 -2
9 1

样例输出:

18
30

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=4145

题目大意:

给你2个大炮和一些敌人,每个大炮的攻击半径为r,A大炮和B大炮的攻击范围分别为r1和r2。问怎样才能使r1*r1 + r2*r2最小。。。

解题思路:

这道题刚开始想错了,以为枚举每个敌人,比较它到2个大炮的距离,如果距离A近,则把这个距离与上个距离A近的敌人的距离比较,取较大者。反之同理处理B。这样就得到A和B炮的半径,进而得到答案。但是这样是错的。比如AB距离为100,他们中点旁边各有1个敌人,根据这种思路得到的距离为49*49 + 49 * 49 = 4802,而如果只用A,则只需要51 * 51 = 2601.所以这种思路是错误的。

正确思路应该是:

将所有敌人距离A的距离从大到小排序,然后枚举A的半径,则B的半径就是A无法覆盖的点中距离B最远的距离。然后用一个变量维护A和B距离的最小值即可。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100010

struct enemy
{
    int x, y, da, db;
}p[N], c1, c2;

bool cmp(enemy a, enemy b)
{
    return a.da < b.da;
}

int dist(enemy a, enemy b)
{
    return ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int main()
{
    int ncase;
    int num;
    int ans, res, onlyb;
    scanf("%d", &ncase);
    while(ncase--)
    {
        scanf("%d%d%d%d", &c1.x, &c1.y, &c2.x, &c2.y);
        scanf("%d", &num);
        for(int i = 0; i < num; ++i)
        {
            scanf("%d%d", &p[i].x, &p[i].y);
            p[i].da = dist(c1, p[i]);
            p[i].db = dist(c2, p[i]);
        }
        sort(p, p + num, cmp);
        res = p[num - 1].da; //b不用
        ans = 0;
        for(int i = num - 2; i >= 0; --i)
        {
            ans = max(ans, p[i + 1].db);
            res = min(res, ans + p[i].da);
        }
        ans = max(ans, p[0].db);
        res = min(res, ans); //a不用
        printf("%d\n", res);
    }
    return 0;
}

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

参考:http://blog.csdn.net/niushuai666/article/details/7174884


  1. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

  2. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。