11
You are given an array/list/vector of pairs of integers representing cartesian coordinates \$(x, y)\$ of points on a 2D Euclidean plane; all coordinates are between \$−10^4\$ and \$10^4\$, duplicates are allowed. Find the area of the convex hull of those points, rounded to the nearest integer; an exact midpoint should be rounded to the closest even integer. You may use floating-point numbers in intermediate computations, but only if you can guarantee that the final result will be always correct. This is code-golf, so the shortest correct program wins.
The convex hull of a set of points \$P\$ is the smallest convex set that contains \$P\$. On the Euclidean plane, for any single point \$(x,y)\$, it is the point itself; for two distinct points, it is the line containing them, for three non-collinear points, it is the triangle that they form, and so forth.
A good visual explanation of what a convex hulls, is best described as imagining all points as nails in a wooden board, and then stretching a rubber band around them to enclose all the points:
Some test cases:
Input: [[50, -13]]
Result: 0
Input: [[-25, -26], [34, -27]]
Result: 0
Input: [[-6, -14], [-48, -45], [21, 25]]
Result: 400
Input: [[4, 30], [5, 37], [-18, 49], [-9, -2]]
Result: 562
Input: [[0, 16], [24, 18], [-43, 36], [39, -29], [3, -38]]
Result: 2978
Input: [[19, -19], [15, 5], [-16, -41], [6, -25], [-42, 1], [12, 19]]
Result: 2118
Input: [[-23, 13], [-13, 13], [-6, -7], [22, 41], [-26, 50], [12, -12], [-23, -7]]
Result: 2307
Input: [[31, -19], [-41, -41], [25, 34], [29, -1], [42, -42], [-34, 32], [19, 33], [40, 39]]
Result: 6037
Input: [[47, 1], [-22, 24], [36, 38], [-17, 4], [41, -3], [-13, 15], [-36, -40], [-13, 35], [-25, 22]]
Result: 3908
Input: [[29, -19], [18, 9], [30, -46], [15, 20], [24, -4], [5, 19], [-44, 4], [-20, -8], [-16, 34], [17, -36]]
Result: 2905
2Do you have any test cases? – Maltysen – 2019-04-14T22:12:38.460
17Not counting whitespace in code golf is a bad idea, it leads to submissions with massive strings of whitespace plus generic code to convert the string to code and execute it. – xnor – 2019-04-14T22:47:06.183
2So if someone can just make a whitespace solution... – attinat – 2019-04-15T00:08:25.543
Related – Giuseppe – 2019-04-15T01:00:01.933
4an exact midpoint should be rounded to the closest even integer: just wondering what's the reasoning behind that? – Arnauld – 2019-04-15T08:47:51.993
@Arnauld Round-to-even is the default rounding mode on IEEE 754 systems. Java and JavaScript mandate rounding towards positive infinity, though.
– nwellnhof – 2019-04-15T11:21:31.3334@nwellnhof True. But enforcing this rule is just an annoyance for languages that don't do it that way (and I think Python 2 doesn't round-to-even either). I don't think we should round at all anyway. The triangle
[[0, 0], [1, 1], [0, 1]]
really should yield $1/2$ rather than $0$. – Arnauld – 2019-04-15T11:49:25.0376Usually challenges are self-contained, but this one isn't. Could you explain what a convex hull is, and how to compute it? Or point to some reference online resource? – Olivier Grégoire – 2019-04-15T12:04:46.737
I've VTCed as unclear until @OlivierGrégoire's comment is addressed. Ping me when it is and I'll retract my vote or vote to reopen. – Shaggy – 2019-04-15T17:11:49.763