ABC202F - Integer Convex Hull
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Score : 600 points
Problem Statement
We have N points P1,P2,…,PN on a plane. The coordinates of Pi is (Xi,Yi). We know that no three points lie on the same line.
For a subset S of {P1,P2,…,PN} with at least three elements, let us define the convex hull of S as follows:
- The convex hull is the convex polygon with the minimum area such that every point of S is within or on the circumference of that polygon.
Find the number, modulo (109+7), of subsets S such that the area of the convex hull is an integer.
Constraints
- 3≤N≤80
- 0≤∣Xi∣,∣Yi∣≤104
- No three points lie on the same line.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X1 Y1 X2 Y2 ⋮ XN YN
Output
Print the answer. Note that you are asked to find the count modulo (109+7).
Sample Input 1
4 0 0 1 2 0 1 1 0
Sample Output 1
2
{P1,P2,P4} and {P2,P3,P4} satisfy the condition.
Sample Input 2
23 -5255 7890 5823 7526 5485 -113 7302 5708 9149 2722 4904 -3918 8566 -3267 -3759 2474 -7286 -1043 -1230 1780 3377 -7044 -2596 -6003 5813 -9452 -9889 -7423 2377 1811 5351 4551 -1354 -9611 4244 1958 8864 -9889 507 -8923 6948 -5016 -6139 2769 4103 9241
Sample Output 2
4060436
ABC202
- Status
- Done
- Rule
- IOI
- Problem
- 7
- Start at
- 2023-6-28 14:15
- End at
- 2023-6-28 16:39
- Duration
- 2.4 hour(s)
- Host
-
梁泽贤 (liangzexian)
- Partic.
- 13