首页 > ACM题库 > HDU-杭电 > hdu 3822 Moving the Mouse待解决[解题报告]C++
2015
04-13

hdu 3822 Moving the Mouse待解决[解题报告]C++

Moving the Mouse

问题描述 :

You know when playing computer games, the mouse is very important. Someone is such a slovenly boy. His desk on which he puts many things is really a mess. For playing games well, he should be able to use the mouse to reach everywhere on screen. His screen’s shape is very strange. It’s a convex polygon so that in order to reach everywhere on screen, he should be able to move his mouse at least everywhere within a convex polygon on the desk. He is too lazy to clean his desk, so he wonders if there is enough space to use his mouse. Can you help him find out if there is enough space? Put it another way, you should find out whether it is possible to put the convex polygon the mouse needs at least on the desk without any intersections with any other things.

You may assume the mouse is just a point and cannot rotate. You may also assume all the things on his desk are convex polygons. Note that these polygons may intersect each other; the mouse can be everywhere on the desk but not be strictly inside any convex polygon of something. You will be given the convex polygons of all the things on his desk and the convex polygon the mouse needs at least.

输入:

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with three integers X, Y, and N. The desk’s lower left coordinates are always (0, 0) and its upper right coordinates are (X, Y). N indicates the number of things on his desk.
Then one line follows. This line contains an integer M followed by M pairs of integers. Each of the pair indicates a vertex of the convex polygon the mouse needs at least. The vertices will be given counterclockwise.
Then N lines follow, each line contains an integer L followed by L pairs of integers. Each of the pair indicates a vertex of the thing’s convex polygon. The vertices will be given counterclockwise.

Technical Specification

1. 1 <= T <= 1000
2. 0 <= N <= 20
3. 3 <= M <= 20
4. 3 <= L <= 20 and all the things are inside the desk.
5. All the coordinates will be greater than or equal to 0 and less than or equal to 10000.

输出:

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with three integers X, Y, and N. The desk’s lower left coordinates are always (0, 0) and its upper right coordinates are (X, Y). N indicates the number of things on his desk.
Then one line follows. This line contains an integer M followed by M pairs of integers. Each of the pair indicates a vertex of the convex polygon the mouse needs at least. The vertices will be given counterclockwise.
Then N lines follow, each line contains an integer L followed by L pairs of integers. Each of the pair indicates a vertex of the thing’s convex polygon. The vertices will be given counterclockwise.

Technical Specification

1. 1 <= T <= 1000
2. 0 <= N <= 20
3. 3 <= M <= 20
4. 3 <= L <= 20 and all the things are inside the desk.
5. All the coordinates will be greater than or equal to 0 and less than or equal to 10000.

样例输入:

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

样例输出:

Case 1: Oh, I have to clean my desk!
Case 2: Yeah, there is enough space!
Case 3: Yeah, there is enough space!

Hint
or the third sample, he can put the mouse in the middle of the desk to reach everywhere within the unit square. See figure below.
Graceful Matrix


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }