P8031 [COCI 2021/2022 #3] Kućice

There are $n$ stalls in a Christmas market. Each stall can be seen as a point in the 2D Cartesian coordinate system, with coordinates $x_i, y_i$. Now each stall violates the rules with probability $50\%$. All violating stalls will be enclosed by a fence, whose shape is the boundary of the convex hull of the points corresponding to all violating stalls. Of course, some innocent stalls that do not violate the rules may also be enclosed. When the number of violating stalls is less than $3$, the convex hull clearly degenerates into a line segment, a point, or the empty set. Find the expected number of stalls that are enclosed. It can be proven that the answer can be written as $\frac{m}{2^n}$, where $m$ is a positive integer. Therefore, you only need to output $m \bmod (10^9+7)$.

The first line contains one positive integer $n$, representing the number of stalls. The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of a stall. The testdata guarantees that no two stalls share the same coordinates, and no three stalls are collinear.

Output $m \bmod (10^9+7)$.

**Sample 1 Explanation** The only stall violates the rules with probability $50\%$, so the expected value is $\frac{1}{2}$. **Sample 2 Explanation** There are $8$ possible violation cases, and the numbers of enclosed stalls in each case are $0, 1, 1, 1, 2, 2, 2, 3$, respectively. Therefore, the expected value is $\frac{1}{8}(0+1+1+1+2+2+2+3)=\frac{12}{8}$. **Constraints** **This problem uses bundled subtasks.** - Subtask 1 (10 pts): Every point lies on the boundary of the convex hull formed by all points, and $n \ge 3$. - Subtask 2 (30 pts): Except for the first point, every point lies on the boundary of the convex hull formed by all points, and $n \ge 4$, $x_1=y_1=0$. - Subtask 3 (10 pts): $1 \le n \le 15$. - Subtask 4 (30 pts): $1 \le n \le 100$. - Subtask 5 (30 pts): No special restrictions. For $100\%$ of the testdata, $1 \le n \le 1000$, $|x_i|, |y_i| \le 10^6$. **Notes** **This problem is translated from [COCI 2021-2022](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf) _Task 5 Kućice_.** **The score of this problem follows the original COCI settings, with a full score of $110$.** Translated by ChatGPT 5