首页 > ACM题库 > HDU-杭电 > hdu 2981 Shoot Your Gun!待解决[解题报告]C++
2014
02-24

hdu 2981 Shoot Your Gun!待解决[解题报告]C++

Shoot Your Gun!

问题描述 :

There are two rectangular polygons (simple polygons with interior angles of only 90 or 270 degrees) G and T , inside another rectangular polygon M . You can place a gun anywhere on the boundary of G , then shoot a bullet in one of four diagonal directions, and then touch the boundary of T . You may shoot across an edge of T , but touching only a corner is also allowed. Your bullet is not allowed to touch G again (even touching a corner of G is not allowed), before touching T .

The edges of M can reflect the bullet. When the bullet touches a vertex of M , it may simply go through it (and not regarded as a reflection), or go back. These special cases are shown in the figure above.

Write a program to find the minimal number of reflections needed from G to T .

输入:

The input contains several test cases. The first line of each case contains three positive integers nG, nT, nM (4<=nG, nT, nM<=50) . The next line contains nG pairs of integers, the coordinates (non-negative integers not greater than 4000) of the vertices of G , in counter-clockwise order. The next two lines describe polygon T and M , in the same format. It is guaranteed that G and T are outside each other (their boundaries will not touch), and are both inside M (they do not touch the boundary of M ). The last test case is followed by a single zero, which should not be processed.

输出:

The input contains several test cases. The first line of each case contains three positive integers nG, nT, nM (4<=nG, nT, nM<=50) . The next line contains nG pairs of integers, the coordinates (non-negative integers not greater than 4000) of the vertices of G , in counter-clockwise order. The next two lines describe polygon T and M , in the same format. It is guaranteed that G and T are outside each other (their boundaries will not touch), and are both inside M (they do not touch the boundary of M ). The last test case is followed by a single zero, which should not be processed.

样例输入:

4 4 12 
1 4 2 4 2 5 1 5 
6 4 7 4 7 5 6 5 
0 3 3 3 3 0 4 0 4 3 8 3 8 6 4 6 4 5 3 5 3 7 0 7 
4 4 4 
1 1 2 1 2 2 1 2 
3 1 4 1 4 2 3 2 
0 0 5 0 5 3 0 3 
4 4 4 
1 1 2 1 2 2 1 2 
6 1 7 1 7 2 6 2  
0 0 8 0 8 3 0 3
0

样例输出:

Case 1: 2 
Case 2: 0 
Case 3: 1


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