| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P147PROJ - ROUND 7J - Chiến hào |
Gần 1 doanh trại quân đội, có 2 hệ thống hào, được mô phỏng bằng các đoạn thẳng trên mặt phẳng. Vào buổi đêm, khi hầu hết chiến sĩ đang ngủ say, 3 người bảo vệ thức để trông các
chiến hào. 2 người bảo vệ có thể nhìn thấy nhau nếu có 1 đường hào giữa 2 người, và không có người bảo vệ thứ 3 giữa 2 người. Vì lí do an ninh, các bảo vệ phải đứng ở vị trí mà mỗi người
có thể nhìn thấy 2 người còn lại. Có bao nhiêu cách xếp chỗ cho họ?
Input
Dòng đầu tiên ghi số bộ test (không quá 20). Mỗi bộ test gồm:
* Dòng đầu tiên chứa số nguyên N( 1<= N<=20), là số lượng rãnh.
* Mỗi N dòng tiếp theo mô tả 1 rãnh: 4 số nguyên X1, Y1, X2, Y2( tất cả nhỏ hơn hoặc bằng 1000), X1, Y1 là tọa độ 1 đầu của rãnh, X2, Y2 là tọa độ đầu còn lại.
Các đường hào có thể chồng chéo và có chung điểm đầu, cuối.
Output
In ra số cách có thể xếp vị trí cho 3 người bảo vệ trên 1 dòng duy nhất.
Example
Input: 3
6
0 0 1 0
0 0 0 1
1 0 1 1
0 1 1 1
0 0 1 1
1 0 0 1
4
5 1 7 1
1 1 5 1
4 0 4 4
7 0 3 4
3
2 2 3 2
3 2 3 3
3 3 2 3 Output: 8
1
0
| Được gửi lên bởi: | adm |
| Ngày: | 2014-03-21 |
| Thời gian chạy: | 5s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 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 |
