Đếm cặp đoạn thẳng cắt nhau

Buổi 07 — Struct & File I/O Implementation Mathematics
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề 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$
Draft saved