Mạng Lưới Cáp Quang
Points
80
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Mạng lưới cáp quang gồm $N$ đoạn dây dẫn thẳng, mỗi đoạn song song với trục $Ox$ (đoạn ngang) hoặc song song với trục $Oy$ (đoạn dọc). Đảm bảo không có hai đoạn ngang nào nằm trên cùng một đường thẳng, và không có hai đoạn dọc nào nằm trên cùng một đường thẳng.
Hai đoạn dây (một ngang, một dọc) được gọi là giao nhau nếu chúng có ít nhất một điểm chung (kể cả tại đầu mút). Hãy đếm tổng số cặp đoạn dây giao nhau.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 10^5$).
- $N$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $x_1, y_1, x_2, y_2$ ($0 \le x_1, y_1, x_2, y_2 \le 10^9$) mô tả một đoạn thẳng nối $(x_1, y_1)$ và $(x_2, y_2)$. Luôn có $x_1 = x_2$ hoặc $y_1 = y_2$ (và hai đầu mút phân biệt).
Kết quả
- In ra một số nguyên duy nhất là số cặp đoạn thẳng giao nhau.
Subtasks
- Subtask 1 (25%): $N \le 1000$.
- Subtask 2 (25%): Các tọa độ nằm trong đoạn $[0, 10^5]$.
- Subtask 3 (50%): Không có ràng buộc bổ sung.
Ví dụ
| Input | Output |
|---|---|
| 4 0 2 5 2 2 0 2 4 4 1 4 3 1 3 6 3 |
4 |
Community Discussion