Đếm cặp đoạn thẳng cắt nhau
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Trên mặt phẳng $Oxy$, cho $N$ đoạn thẳng. Mỗi đoạn thẳng được biểu diễn bởi struct Segment { Point a, b; }. Hai đoạn thẳng được coi là cắt nhau nếu chúng có ít nhất một điểm chung (kể cả tại đầu mút hoặc trùng nhau một phần). Hãy đếm số cặp đoạn thẳng $(i, j)$ với $i < j$ cắt nhau.
Dữ liệu vào
Dòng đầu chứa số nguyên $N$. $N$ dòng tiếp theo, mỗi dòng gồm 4 số nguyên $x_1, y_1, x_2, y_2$ là tọa độ hai đầu mút của một đoạn thẳng.
Dữ liệu ra
Một số nguyên duy nhất là số cặp đoạn thẳng cắt nhau.
Ví dụ
| Input | Output |
|---|---|
| 3 0 0 4 4 0 4 4 0 5 5 6 6 |
1 |
| 2 0 0 2 0 2 0 4 0 |
1 |
Giới hạn
- $2 \le N \le 200$
- $-10^4 \le x_1, y_1, x_2, y_2 \le 10^4$
Community Discussion