Phân loại tứ giác
Đề bài
Mô tả
Tuấn vừa học về các loại tứ giác và muốn thử khả năng nhận biết của mình.
Cho điểm trên mặt phẳng tọa độ , được đánh số từ đến . Hai hay nhiều điểm ban đầu có thể trùng tọa độ.
Tuấn chọn một bộ điểm có chỉ số khác nhau với . Một bộ điểm được coi là một tứ giác hợp lệ nếu thỏa mãn đồng thời hai điều kiện:
- Bốn điểm được chọn có tọa độ đôi một khác nhau.
- Không có ba điểm nào trong bốn điểm được chọn thẳng hàng.
Mỗi bộ chỉ số khác nhau được tính là một cách chọn riêng, kể cả khi một số điểm trùng tọa độ.
Với mỗi bộ điểm hợp lệ, hãy xác định chúng tạo thành những loại tứ giác nào:
- Hình vuông (S): có cạnh bằng nhau và góc vuông.
- Hình chữ nhật (R): có góc vuông.
- Hình thoi (H): có cạnh bằng nhau.
- Hình thang (T): có ít nhất cặp cạnh đối song song.
- Hình bình hành (P): có cặp cạnh đối song song.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên ().
- dòng tiếp theo, dòng thứ chứa hai số nguyên () là tọa độ điểm thứ .
Dữ liệu ra
In ra số nguyên trên một dòng, cách nhau bởi dấu cách, lần lượt là số bộ điểm tạo thành hình vuông (S), hình chữ nhật (R), hình thoi (H), hình thang (T) và hình bình hành (P).
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 0 0 0 1 0 1 1 0 1 1 |
2 2 2 2 2 | Điểm và điểm trùng tọa độ . Có hai bộ hợp lệ là và , cả hai đều là hình vuông cạnh ; một hình vuông đồng thời là hình chữ nhật, hình thoi, hình thang và hình bình hành. Các bộ còn lại chứa cả điểm và điểm nên không hợp lệ. |
| 4 0 0 4 0 3 2 1 2 |
0 0 0 1 0 | Bốn điểm tạo thành hình thang có hai đáy nằm trên các đường và ; hai cạnh bên không song song nên không phải hình bình hành. |
Bình luận