首页 > ACM题库 > HDU-杭电 > hdu 1959 Watchdog-模拟[解题报告]C++
2013
12-26

hdu 1959 Watchdog-模拟[解题报告]C++

Watchdog

问题描述 :

A company (name withheld) has an office building in the center of Lund. The building has a perfectly square roof with a number of hatches. Because of a series of burglaries where the perpetrators have entered through these hatches, it was decided to use a watchdog to guard the hatches. A particularly vicious but rather stupid breed of dog was chosen, and unfortunately the dog fell off the roof on its third watch.

A new dog has been procured and it has been decided to attach a leash to its collar and attach the other end at some point on the roof. However, if the leash is too short the dog cannot reach all hatches, but if it is too long then the dog will fall off the building again. The leash has hooks at both ends, so no part of it is used to tie knots. The company wants the dog to reach the center of each hatch (the dog can reach exactly as far as the leash could reach if it were lying flat on the roof), but it does not want the leash to extend beyond the edge of the roof (to the edge is OK). They hope that by carefully choosing the length of the leash and where to attach it, the dog will be able to reach all hatches without risking falling off the building. A leash can only be attached at a point with integer coordinates (if the building is 10 by 10 meters, then the south-west corner of the building has coordinates (0, 0) and the north-east corner has coordinates (10, 10)). A leash cannot be attached at a point where there is a hatch.

If there is no place where you can attach a leash, reach all hatches but not reach beyond the edge of the roof, it is impossible to use this breed of dog, and the company will instead use a poodle (which is a less vicious type of dog, but also less prone to falling off buildings).

输入:

On the first line of the input is a single positive integer N, telling the number of test cases to follow. Each case starts with one line with two integers S H, where S is even, 2 <= S <= 40, and 1 <= H <= 50. S is the side of the square roof in meters and H is the number of hatches. The following H lines each contain two integers X and Y. These are the coordinates of the hatches. Hatches will never lie outside the roof or on the roof’s perimeter. No two hatches will occupy the same position

输出:

On the first line of the input is a single positive integer N, telling the number of test cases to follow. Each case starts with one line with two integers S H, where S is even, 2 <= S <= 40, and 1 <= H <= 50. S is the side of the square roof in meters and H is the number of hatches. The following H lines each contain two integers X and Y. These are the coordinates of the hatches. Hatches will never lie outside the roof or on the roof’s perimeter. No two hatches will occupy the same position

样例输入:

3
10 2
6 6
5 4
20 2
1 1
19 19
10 3
1 1
1 2
1 3

样例输出:

3 6
poodle
2 2


题目大意:
Description
A company (name withheld) has an office building in the center of Lund.
一个叫withheld的公司在Lund的中心建了一座办公楼。
The building has a perfectly square roof with a number of hatches.
这座楼的屋顶是正方形的,在屋顶上有一些窗口。
Because of a series of burglaries where the perpetrators have entered through these hatches,
因为有一些小偷会通过这些窗口进来偷盗,
it was decided to use a watchdog to guard the hatches.
所以要用一只看门狗来守卫这些窗口。
A particularly vicious but rather stupid breed of dog was chosen, and unfortunately the dog fell off the roof on its third watch.
一只比较凶猛但是比较蠢的狗被选中了,但不幸的是,在第三次看守的时候他从屋顶掉下去了。
A new dog has been procured and it has been decided to attach a leash to its collar and attach the other end at some point on the roof.
现在又选了另一只狗,现在决定用一根绳子绑在他的脖子上,绳子的另一端绑在屋顶的某个位置上。
However, if the leash is too short the dog cannot reach all hatches,
然而,如果这绳子太长的话,狗就不能到达所有的窗口,
but if it is too long then the dog will fall off the building again.
但是如果太长的话狗就有可能再一次掉下屋顶。
The leash has hooks at both ends, so no part of it is used to tie knots.
绳子的两端都已经固定了,所以绳子是不会打结的。
The company wants the dog to reach the center of each hatch (the dog can reach exactly as far as the leash could reach if it were lying flat on the roof),
该公司想要这只狗能够到达所有的窗口(狗可以到达绳子所有到达的地方,只要那个点还在屋顶上),
but it does not want the leash to extend beyond the edge of the roof (to the edge is OK).
但是它不想绳子能申长到屋顶以外的地方(在屋顶的边缘是没关系的)。
They hope that by carefully choosing the length of the leash and where to attach it, the dog will be able to reach all hatches without risking falling off the building.
他们想要选择合适的绳子长度和绑绳子的位置,使得狗刚刚好能够到达所有的窗口,而且不会有掉下去的危险。
A leash can only be attached at a point with integer coordinates (if the building is 10 by 10 meters, then the south-west corner of the building has coordinates (0, 0) and the north-east corner has coordinates (10, 10)).
绳子只能被系在整点座标上(如果这个建筑物是10*10米,那么西南角的座标是(0,0)而东北角的座标是(10,10))。
A leash cannot be attached at a point where there is a hatch.
绳子不能被系在有窗口的点上。
If there is no place where you can attach a leash, reach all hatches but not reach beyond the edge of the roof, it is impossible to use this breed of dog, and the company will instead use a poodle (which is a less vicious type of dog, but also less prone to falling off buildings).
如果没有找到合适的点系绳子,那么就不能用狗来看守窗口了,公司会用贵宾犬来代替普通狗(这种狗没有之前的凶猛,但是不易掉下屋顶)。
Input
On the first line of the input is a single positive integer N, telling the number of test cases to follow.
第一行是一个N,代表有几组测试数据。
Each case starts with one line with two integers S H, where S is even, 2 <= S <= 40,and 1 <= H <= 50. S is the side of the square roof in meters and H is the number of hatches.
每一个数据以两个整数S H开头,其中S是偶数,2 <= S <= 40,1 <= H <= 50。S是屋顶的边长,H是窗口的数目。

The following H lines each contain two integers X and Y.
接下来H行,每一行是两个整数X和Y。
These are the coordinates of the hatches.
这些代表的是窗口的座标。
Hatches will never lie outside the roof or on the roof's perimeter.
窗口不会座落在屋顶之外。
No two hatches will occupy the same position
没有两个窗口会占着同一个位置。
Output
For each test case, output one line containing the coordinates X Y at which to fasten the leash
对于每一个数据,输出绳子所系的点座标
(if there are several possible points, output the one with smallest X, and if there are still several possibilities select the one with smallest Y among those with smallest X)
(如果有多个解,就输出X最小的,如果还是有多个解,就选择X最小中的Y最小的)
If there is no such point, output "poodle" for that test case.
如果没有解,就输出poodle

解题报告:这题的难点在于理解题意,看懂了题目之后,应该没什么难度,直接枚举绳子系的点,再计算出长度,看看会不会超出边界。

复杂度O(S*S*H)无压力。

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
  
using namespace std;
typedef __int64 lld;
const int MAX=51;
  
const int INF=1000000001;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
const int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
bool used[MAX][MAX];
struct Point
{
    int x,y;
}p[MAX];
bool ok(int x,int y,int len,int n)
{
    int i,tx,ty;
    for(i=0;i<n;i++)
    {
        tx=x-p[i].x;
        ty=y-p[i].y;
        if(tx*tx+ty*ty>len)return false;
    }
    return true;
}
int main()
{
    int n,m;
    int T;
    scanf("%d",&T);
    while(T–)
    {
        scanf("%d%d",&n,&m);
        memset(used,false,sizeof(used));
        int i,j;
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&p[i].x,&p[i].y);
            used[p[i].x][p[i].y]=true;
        }
  
        int ax=-1,ay=-1;
        for(i=0;i<=n&&ax==-1;i++)
        {
            for(j=0;j<=n&&ax==-1;j++)
            {
                if(used[i][j])continue;
                int len=i;
                if(n-i<len)len=n-i;
                if(j<len)len=j;
                if(n-j<len)len=n-j;
                if(ok(i,j,len*len,m))
                {
                    ax=i;
                    ay=j;
                }
            }
        }
  
        if(ax!=-1)
        {
            printf("%d %d\n",ax,ay);
        }
        else puts("poodle");
    }
    return 0;
}
/*
3
10 2
6 6
5 4
  
20 2
1 1
19 19
  
10 3
1 1
1 2
1 3
  
*/

 


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

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

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