题目描述
平面直角坐标系中求一个凸包的周长 C。
输入描述
第一行输入一个 n ,代表测试数据量
接下来 n 行输入 nn 个坐标 (x,y)
1≤n≤5×10^4,∣x∣,∣y∣≤10^4
输出描述
输出 C, 结果保留 6位小数。
输入输出样例
示例 1
输入
1. 4 2. 4 8 3. 4 12 4. 5 9.3 5. 7 8
输出
12.000000
运行限制
- 最大运行时间：3s
- 最大运行内存: 256M
思路
核心思想：
凸包算法的基本思路是 旋转扫除，即设定一个参照顶点，逐个旋转到其它所有顶点，并判断这些顶点是否在凸包上。算法做两次扫描，先从最左边的点沿“下凸包”扫描到最右边，再从最右边的点沿“上凸包”扫描到最左边，“上凸包”和“下凸包”合起来就是完整的凸包。
具体过程：
1.我们把所有的点按照横坐标 x 从小到大进行排序，如果 x 相同，按 y 从小到大排序。并删除重复的点。
2.我们找到最左边的点，p0一定在凸包上，从左往右扫描，如果发现新点在凸包“前进”方向的左边，说明在“下凸包”上，把它加入到凸包；如果在右边，说明拐弯了，删除最近加入下凸包的点。继续这个过程，直到检查完所有点。
注：拐弯方向用叉积判断即可。当叉积为<=0时，说明前进的方向在新点的左侧，要删除刚才加入的点，加上我们的新点。
3.再从右往左扫描点，注意我们这里直接将已经排好序的点逆序遍历，叉积的判断代码不变，依旧是左旋（左是相对于前进路线而言）。最后要记得pop出最后一个节点，因为这个节点就是我们一开始的p[0]点，其实不进行这一步也是可以的，因为我们最终通过点的坐标来累加周长，相同的点之间的距离为0，对结果无影响。
4.我们得到了所有的点，只需依次累加两个相邻点之间的距离即可
代码
1. from decimal import * 2. from math import sqrt 3. 4. class Point: 5. def __init__(self, x=0, y=0): 6. self.x = x 7. self.y = y 8. #重写运算符“==”，“+”，“-”，“*” 9. def __eq__(self, other): 10. return self.x == other.x and self.y == other.y 11. def __add__(self, other): 12. return Point(self.x + other.x, self.y + other.y) 13. def __sub__(self, other): 14. return Point(self.x - other.x, self.y - other.y) 15. def __mul__(self, other): 16. return self.x * other.x + self.y * other.y 17. #__repr__() 方法是类的实例化对象用来做“自我介绍”的方法， 18. #默认情况下，它会返回当前对象的“类名+object at+内存地址”， 19. #而如果对该方法进行重写，可以为其制作自定义的自我描述信息。 20. def __repr__(self): 21. return str(self.x) + " " + str(self.y) 22. 23. #通过两个向量计算叉乘 24. def cross(a, b): 25. return a.x * b.y - a.y * b.x 26. #通过三个点计算向量ab和ac的叉乘 27. def clockwise(a, b, c): 28. return cross(b - a, c - a) 29. #计算平方 30. def square(x): 31. return x * x 32. #计算平方和 33. def dis2(a, b): 34. return square(a.x - b.x) + square(a.y - b.y) 35. #计算两点距离 36. def dis(a, b): 37. return sqrt(dis2(a, b)) 38. #遍历两次 39. def convex_hull(p): 40. def cmp(a): 41. return a.x * 100000 + a.y 42. p = sorted(p, key=cmp) 43. n = len(p) 44. stk = [] 45. stk.append(p[0]) 46. for i in p[1:]: 47. while len(stk) > 1 and cross(stk[-1] - stk[-2], i - stk[-2]) <= 0: 48. del stk[-1] 49. stk.append(i) 50. tmp = len(stk) 51. 52. for i in p[::-1]: 53. #还是左旋 54. while len(stk) > tmp and cross(stk[-1] - stk[-2], i - stk[-2]) <= 0: 55. del stk[-1] 56. stk.append(i) 57. stk.pop() 58. return stk 59. 60. #设置小数点的精度 61. #getcontext().prec = 50 62. 63. n = int(input()) 64. p = [Point() for i in range(n)] 65. for i in p: 66. i.x, i.y = map(Decimal, input().split()) 67. 68. convex = convex_hull(p) 69. C = 0 70. for i in range(len(convex)): 71. C += dis(convex[i - 1], convex[i]) 72. print("%.6f" % C)
