| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P181PROJ - ROUND 1J - Đa tam giác |
Cho một đa giác N đỉnh không tự cắt ( không có 2 cạnh nào cắt nhau, không hẳn là đa giác lồi). Ta cần chia đa giác này thành nhiều tam giác, thỏa mãn những điều sau:
- Mỗi đỉnh của mỗi tam giác là một đỉnh của đa giác.
- Mỗi cạnh của đa giác phải là cạnh của một tam giác nào đó.
- Diện tích giao nhau giữa 2 tam giác bằng không và tổng diện tích tất cả tam giác đúng bằng diện tích đa giác.
- Mỗi cạnh bên của tam giác có 2 đầu mút là 2 đỉnh của đa giác.
- Tất cả tam giác đều phải nằm trong đa giác.
Dưới đây là ví dụ về một cách chia thỏa mãn.
Hãy đếm số cách chia đa giác thành các tam giác thỏa mãn, kết quả lấy dư cho 10^9+7.
Input
Dòng đầu tiên là số n ( 3 ≤ n ≤ 200) – số đỉnh của đa giác.
N dòng tiếp theo mỗi dòng chứa 2 số nguyên (x , y) là tọa độ của mỗi đỉnh của đa giác theo thứ tự thuận chiều kim đồng hồ, hoặc ngược chiều kim đồng hồ. (|x|, |y| ≤ 10^7)
Output
Kết quả bài toán lấy dư cho 10^9+7.
Example
Input:
4
0 0
1 0
0 1
-1 0
Output:
1
Input:
5
0 0
1 0
1 1
0 1
-2 -1
Output:
3
| Được gửi lên bởi: | adm |
| Ngày: | 2018-03-02 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
