HDU 1392 Surround the Trees

  • 2018-08-10
  • 7
  • 0

Description:

There are a lot of trees in an area. A peasant wants to buy a rope to surround all these trees. So at first he must know the minimal required length of the rope. However, he does not know how to calculate it. Can you help him?
The diameter and length of the trees are omitted, which means a tree can be seen as a point. The thickness of the rope is also omitted which means a rope can be seen as a line.

img

There are no more than 100 trees.

Input:

The input contains one or more data sets. At first line of each input data set is number of trees in this data set, it is followed by series of coordinates of the trees. Each coordinate is a positive integer pair, and each integer is less than 32767. Each pair is separated by blank.

Zero at line for number of trees terminates the input for your program.

Output:

The minimal length of the rope. The precision should be 10^-2.

Sample Input:

9
12 7
24 9
30 5
41 9
80 7
50 87
22 9
45 1
50 7
0

Sample Output:

243.06

题目链接

求一个简单凸包,模板题。

先找到基准点(最左下角),之后将其他点按照极角排序,遍历顶点依次用叉乘判断当前顶点和上一个顶点构成的线段是否在上一个顶点和上上个顶点构成线段的顺时针方向,若是则上一个顶点不属于构成结果的多边形中,若不是则上一个顶点在构成结果的多边形中,最后求和即可。

注意特判一个点以及两个点的情况。

AC代码:

评论

还没有任何评论,你来说两句吧