CSES - Intersection Points | Giao điểm
Xem PDF
Điểm:
1700 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho \(n\) đoạn thẳng theo phương ngang và dọc, bạn hãy tính số lượng giao điểm.
Không có cặp đoạn thẳng song song nào có điểm chung, và không có đầu mút của đoạn thẳng nào là giao điểm.
Input
Dòng đầu tiên chứa \(n\): số lượng đoạn thẳng.
Sau đó là \(n\) dòng mô tả các đoạn thẳng. Mỗi dòng có bốn số nguyên \(x_1, y_1, x_2\) và \(y_2\): một đoạn thẳng bắt đầu tại điểm \((x_1,y_1)\) và kết thúc tại điểm \((x_2,y_2)\).
Output
In ra số giao điểm
Constraints
- \(1≤n≤10^5\)
- \(−10^6≤x_1≤x_2≤10^6\)
- \(−10^6≤y_1≤y_2≤10^6\)
- \((x1,y1)≠(x2,y2)\)
Example
Sample Input:
3
2 3 7 3
3 1 3 5
6 2 6 6
Sample Output:
2
Bình luận
CSES - Intersection Points | Giao điểm
Cho \(n\) đoạn thẳng theo phương ngang và dọc, nhiệm vụ của bạn là tính số giao điểm của chúng.
Dữ liệu đảm bảo không có cặp đoạn thẳng song song nào có điểm chung, và không có đầu mút của đoạn thẳng nào là giao điểm.
Input
Output
Test 1
Input
Output