COCI '21 Contest 3 #5 Kućice

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 0.5s
Memory limit: 512M

Problem type

Everyone knows that every other booth at the Zagreb Christmas Market was actually set up just by pulling the right strings. This year the authorities have decided to send an inspection to penalize the booths that were set up illegitimately.

There are n booths, which can be represented by points in the plane, where no three of them lie on the same line. The authorities will identify the booths ruled by corruption and fence them off from the rest of the town. The fence will surround the mentioned booths, and it will form the shape of the smallest convex polygon containing all of them. In other words, the fence can be thought of as the boundary of the convex hull of the chosen set of points. Unfortunately, it's possible that some of the innocent booths become fenced off as well.

Before an on-site inspection, the authorities estimate that the probability of corruption of any particular booth is 50\%. Having this in mind, they wonder what is the expected number of booths that will end up being fenced off. The expected value is defined by multiplying the probability of a certain subset of booths being chosen by the number of booths fenced off in that choice and summing this up for all possible choices of the subset. Of course, if the chosen subset consists of less than three points, the convex hull is degenerate, i.e., a segment, point or the empty set.

It can be proven that the desired expected value can be written in the form \frac{m}{2^n}, for some positive integer m. The authorities would like to know the expected value, so they kindly ask you to compute the value of m. Since the answer can be very large, you should print it modulo 10^9 + 7.

Input Specification

The first line contains a positive integer n (1 \le n \le 1\,000), the number of booths.

The i^\text{th} of the next n lines contains a pair of integers x_i, y_i (|x_i|, |y_i| \le 10^6), which represent the x and y coordinates of the i^\text{th} booth, respectively. No two booths have the same location.

No three booths will lie on the same line.

Output Specification

In the only line, print the number m described above, modulo 10^9 + 7.


110All points are on the boundary of the convex hull of all points and n \ge 3.
230All points except the first one are on the boundary of the convex hull of all points, which is in the interior, and n \ge 4, x_1 = y_1 = 0.
3101 \le n \le 15
4301 \le n \le 100
530No additional constraints.

Sample Input 1

5 5

Sample Output 1


Explanation for Sample Output 1

There is a probability of 50\% that the first and only booth gets fenced off, so the expected value is \frac{1}{2}.

Sample Input 2

-1 -1
1 -1
0 1

Sample Output 2


Explanation for Sample Output 2

There are eight possible choices for a subset, and the number of fenced off booths for those choices is 0, 1, 1, 1, 2, 2, 2, 3. The expected value is then \frac{1}{8}(0 + 1 + 1 + 1 + 2 + 2 + 2 + 3) = \frac{12}{8}.

Sample Input 3

0 0
-1 0
2 -1
3 2
0 3

Sample Output 3



There are no comments at the moment.