### P_Nyagolov's blog

By P_Nyagolov, history, 4 years ago, Hello everybody,

Recently, while exploring vjudge, I came across this problem and I have no idea how to solve it.

Basically, we are given N points (N ≤ 1000), no three points lie on the same line, and we are to find the sum of areas of the convex hulls for each subset of at least 3 points. There are multiple test cases and the sum of the N values over all test cases is up to 5000.  Comments (3)
 » Probably the same solution as the one mentioned by hex539 but explained with details:Fix two points. The segment between these two points will be a part of some number of hulls. To count them, we first notice that this segment may be both clockwise or counterclockwise oriented. If the orientation is clockwise, we can draw a line through these two points and count the number of points above the line. Let this number be C. Then the number of convex hulls in which this segment appears in clockwise direction is 2C - 1. Similarly it appears in counterclockwise direction 2N - C - 2 - 1 times. From here we get an obvious solution.To get a solution, we first fix a point and sort every by angle with the fixed one. Well now we simply have to do a sweep line algorithm, keeping two pointers. There probably is a smarter solution but this should work.