Expert · Geometry · 264 of 264
Fence around the trees
Build the smallest convex fence around all the trees (the convex hull). Print how many trees are corners of the fence (trees in the middle of a straight side do not count) and the fence length with two decimals.
Input: n (at least 3, not all in a line), then n lines "x y". Output: <corners> <perimeter>
Examples
Input
5 0 0 2 0 1 1 2 2 0 2
Output
4 8.00
Input
3 0 0 3 0 0 4
Output
3 12.00
Input
6 0 0 1 0 2 0 2 2 0 2 1 1
Output
4 8.00
One more test checks other inputs when you press Check.
Stuck? The idea behind geometry
Points as (x, y) pairs. The cross product of two vectors says which way they turn: positive left, negative right, zero in line.
The shoelace formula gives a polygon's area from its corners in order.
pts = [(0, 0), (4, 0), (4, 3)]
area = 0
for i in range(len(pts)):
x1, y1 = pts[i]
x2, y2 = pts[(i + 1) % len(pts)]
area += x1 * y2 - x2 * y1
print(abs(area) / 2) # 6.0Watch for: Decimals add up small errors: keep whole numbers as long as you can and compare with care.