首页 > ACM题库 > HDU-杭电 > hdu 2684 Astar待解决[解题报告]C++
2014
02-13

hdu 2684 Astar待解决[解题报告]C++

Astar

问题描述 :

A 3-dimensional shape is said to be convex if the line segment joining any two points in the shape is entirely contained within the shape. Given a general set of points X in 3-dimensional space, the convex hull of X is the smallest convex shape containing all the points.
For example, consider X = {(0, 0, 0), (10, 0, 0), (0, 10, 0), (0, 0, 10)}. The convex hull of X is the tetrahedron with vertices given by X.

Given X, your task is to find the girth of the convex hull of X, rounded to the nearest integer.

You may assume there will be at most 3 points in X on any face of the convex hull.

输入:

The input test file will contain multiple test cases, each of which begins with an integer n (4 ≤ n ≤ 25) indicating the number of points in X. This is followed by n lines, each containing 3 integers giving the x, y and z coordinate of a single point. All coordinates are between −100 and 100 inclusive. The end-of-file is marked by a test case with n = 0 and should not be processed.

输出:

The input test file will contain multiple test cases, each of which begins with an integer n (4 ≤ n ≤ 25) indicating the number of points in X. This is followed by n lines, each containing 3 integers giving the x, y and z coordinate of a single point. All coordinates are between −100 and 100 inclusive. The end-of-file is marked by a test case with n = 0 and should not be processed.

样例输入:

5
0 0 0
10 0 0
0 10 0
0 0 10
1 1 1

4
0 0 0
1 0 0
0 1 0
0 0 1
0

样例输出:

72
7


  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  2. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

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