MSE06H - Japan
Giới hạn- Thời gian: 0.209s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Japan chuẩn bị chào đón ACM ICPC World Finals và muốn xây 1 số đường. Japan là 1 hòn đảo với N thành phố ở bờ phía Đông và M thành phần ở bờ phía Tây, (M ≤ 1000, N ≤ 1000). Các thành phố ở mỗi bờ được đánh số từ 1 trở đi theo chiều từ Bắc tới Nam. K superhighways sẽ được xây để nối bờ phía Đông và bờ phía Tây của Japan. Mỗi superhighway là 1 đường thẳng nối 1 thành phố ở bờ Đông và 1 thành phố ở bờ Tây.
Xác định số giao điểm của các đường cao tốc này. Không có 3 đường cao tốc cắt nhau tại 1 điểm.
Dòng đầu của file Input là T - số test. Mỗi test bắt đầu bởi 3 số – N, M, K. Tiếp theo là K dòng, mỗi dòng 2 số mô tả cặp thành phố được nối bởi đường cao tốc (số thứ nhất ở bờ Đông, số thứ hai ở bờ Tây)
Với mỗi test case, in ra 1 dòng có dạng :
Test case "case number": "số giao điểm"
Sample
Input : 1 3 4 4 1 4 2 3 3 2 3 1 Ouput: Test case 1: 5
- Người up: vdmedragon
- Nguồn bài: Southeastern European 2006