Kućice
레이팅 미적용의견: 0
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-si\)te 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 which 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 ^{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\).
Subtask 1 (10 points): All points are on the boundary of the convex hull of all points and \(n \ge 3\).
Subtask 2 (30 points): All points except the first one are on the boundary of the convex hull of all points, which is is the interior, and \(n \ge 4\), \(x_{1} = y_{1} = 0\).
Subtask 3 (10 points): \(1 \le n \le 15\)
Subtask 4 (30 points): \(1 \le n \le 100\)
Subtask 5 (30 points): No additional constraints.
The first line contains a positive integer \(n\) (\(1 \le n \le 1000\)), the number of booths.
The \(i-th\) of the next \(n\) lines contains a pair of positive integers \(x@@RISE_MATH_BLOCK_0@@i\) (|\(x@@RISE_MATH_BLOCK_1@@i\)| ≤\(10^{6}\)), which represent the
\(x\) and \(y\) coordinates of the \(i-th\) booth, respectively. No two booths have the same location.
No three booths will lie on the same line.
In the only line print the number \(m\) described above, modulo \(10^{9} + 7\).
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | All points are on the boundary of the convex hull of all points and \(n \ge 3\). |
2 | 30점 | All points except the first one are on the boundary of the convex hull of all points, which is is the interior, and \(n \ge 4\), \(x_{1} = y_{1} = 0\). |
3 | 10점 | \(1 \le n \le 15\) |
4 | 30점 | \(1 \le n \le 100\) |
5 | 30점 | No additional constraints. |
1
5 513
-1 -1
1 -1
0 1125
0 0
-1 0
2 -1
3 2
0 383Clarification of the first example:
There is a probability of 50% that the first and only booth gets fenced off, so the expected value is 1
2.
Clarification of the second example:
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 1
8(0 + 1 + 1 + 1 + 2 + 2 + 2 + 3) = 12
8 .
평가 및 의견
Kućice
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Kućice