| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT137E - BÀI E - ĐA GIÁC GIAO NHAU |
Bài toán đặt ra là cho trước một tập các đa giác trên không gian hai chiều. Hãy xác định xem các đa giác nào là giao nhau.
Input
Dòng đầu tiên chứa số n là số bộ test (không quá 100). Mỗi bộ test gồm:
- Một dòng chứa số nguyên dương m là số đa giác (1<=m<=10)
- m dòng tiếp theo, mỗi dòng ghi ra biểu diễn một đa giác theo thứ tự từ 1 đến m.
- Mỗi đa giác bắt đầu với số v (3<=v<=20) là số đỉnh.
- Tiếp theo là v cặp số nguyên (x,y) là tọa độ của từng đỉnh. Các cạnh của đa giác sẽ nối theo thứ tự từ đỉnh 1 đến 2 … đến v. Đỉnh v nối với đỉnh 1. Chú ý: các đa giác đều được đảm bảo là đa giác đơn.
Output
- Với mỗi bộ test, in ra màn hình thứ tự bộ test (DATASET #x với x là thứ tự bộ test) sau đó lần lượt liệt kê các cặp đa giác giao nhau theo thứ tự từ nhỏ đến lớn, mỗi cặp trên một dòng (mỗi cặp viết đa giác có thứ tự nhỏ hơn trước).
- Nếu không có cặp đa giác nào giao nhau thì in ra dòng chữ: no collisions
Example
Input:
2
2
4 0,0 1,0 1,1 0,1
4 2,2 3,2 3,3 2,3
4
3 2,1 1,2 2,3
3 2,1 3,2 2,3
5 2,0 4,2 2,4 5,4 5,0
4 3,3 1,3 1,5 3,5
Output:
Data Set #1
no collisions
Data Set #2
1 2
1 4
2 4
3 4
| Được gửi lên bởi: | adm |
| Ngày: | 2013-03-24 |
| 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 |
