首页 > ACM题库 > HDU-杭电 > hdu 3227 Heroes Arrangement待解决[解题报告]C++
2014
03-09

hdu 3227 Heroes Arrangement待解决[解题报告]C++

Heroes Arrangement

问题描述 :

There are N heroes in the Kingdom of Heroes, each hero has a special range of activity, this “range” is a delta-shaped region (triangle region including the boundary; it is guaranteed that all triangles will neither degenerate into a segment nor a point on the King’s angle of view), and heroes can appear in any point in his activity range. The king, standing at the Origin (0, 0, 0), is observing the heroes. No range of activity will contain the king’s position.

You may assume that no hero could meet others, that means these “range” have no common point. Your task is to find number K, indicating that the king can choose at most K heroes such that no pairs of chosen heroes cause one may block the king’s view line to observe another. In other words, no hero can appear on the segment between another hero and the King.

输入:

There are multiple test cases, the number of them, T, is given in the very first line of the input, followed by T cases.

For each test case:
First line contains an integer N, the number of heroes, 1≤N≤40. Then N lines follow, each line contains nine integers x1 y1 z1 x2 y2 z2 x3 y3 z3, denoting the coordinates of the delta-shaped regions’ vertex respectively, -100≤x1, y1, z1, x2, y2, z2, x3, y3, z3≤100.

输出:

There are multiple test cases, the number of them, T, is given in the very first line of the input, followed by T cases.

For each test case:
First line contains an integer N, the number of heroes, 1≤N≤40. Then N lines follow, each line contains nine integers x1 y1 z1 x2 y2 z2 x3 y3 z3, denoting the coordinates of the delta-shaped regions’ vertex respectively, -100≤x1, y1, z1, x2, y2, z2, x3, y3, z3≤100.

样例输入:

2
2
0 0 1 1 2 1 -1 2 1
0 0 2 1 -2 2 -1 -2 2
2
0 0 1 1 2 1 -1 2 1
0 0 -1 1 -2 -1 -1 -2 -1

样例输出:

Case #1: 1
Case #2: 2
Hint
The sample image of the sample input is drawn below, the small sphere is the position of the king.
Game Simulator


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }