Convex Polygons

View as PDF

Submit solution

Points: 1.51 (partial)
Time limit: 2.85s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Code Craft 09
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho ~n~ điểm trong hệ tọa độ Descartes ~2D~. Bạn phải tính số lượng đa giác lồi có lớn hơn hoặc bằng ~3~ đỉnh mà có thể tạo thành bằng cách chọn một tập hợp con trong tập hợp các điểm đã cho. Để đơn giản, dữ liệu vào đảm bảo các điều kiện sau:

  • Không có ~3~ điểm bất kỳ nào thẳng hàng.
  • Không có ~2~ điểm nào có cùng tọa độ.

Do kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho ~1234567~

Input

Dòng đầu chứa số nguyên ~T~, số lượng test. Trong mỗi test:

  • Dòng đầu chứa ~n~ là số lượng điểm của test đó;
  • ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~2~ số nguyên là tọa độ của điểm thứ ~i~. Trị tuyệt đối của các tọa độ không quá ~10000~.

Output

~T~ dòng, mỗi dòng ghi đáp án cho test tương ứng.

Giới hạn

Input Set ~1~: ~T \leq 100;\text{ }3 \leq n \leq 10~.

Input Set ~2~: ~T \leq 50;\text{ }3 \leq n \leq 100~.

Sample Input

2
4
0 0
2 0
2 2
0 2
6
0 0
2 0
2 2
0 2
1 -1
1 3

Sample Output

5
42

Comments

Please read the guidelines before commenting.


There are no comments at the moment.