COLOREC - VOI 2011 Hình chữ nhật bốn màu
Giới hạn- Thời gian: 0.6s
- 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.
Trên mặt phẳng tọa độ Đề các vuông góc Oxy cho n điểm phân biệt Ai(xi, yi) i = 1, 2, 3, …, n. Mỗi điểm Ai được tô bởi màu Ci thuộc {1, 2, 3, 4}. Ta gọi hình chữ nhật bốn màu là hình chữ nhật thỏa mãn hai điều kiện sau:
- Bốn đỉnh của hình chử nhật là bốn điểm trong n điểm đã cho và được tô bởi bốn màu khác nhau.
- Các cạnh của hình chử nhật song song với một trong hai trục tọa độ.
Yêu cầu: Cho biết tọa độ và màu của n điểm, hãy đếm số lượng hình chữ nhật bốn màu.
Dữ liệu:
- Dòng đầu tiên chứa số nguyên dương n (4 <= n <= 10^5) là số lượng điểm trên mặt phẳng.
- Dòng thứ i trong n dòng tiếp theo chứa ba số nguyên xi, yi, ci (|xi|, |yi| <= 200) là thông tin về tọa độ và màu của điểm thứ i (i = 1, 2, 3, .., n).
- Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra trên một dòng số lượng hình chữ nhật đếm được.
Ví dụ:
Input
7 0 0 1 0 1 4 2 1 2 2 -1 3 0 -1 1 -1 -1 4 -1 1 1
Output
2
Ràng buộc: 50% số test ứng với 50% số điểm của bài có 4 <= n <= 100
- Người up: voj
- Nguồn bài: VOI 2011