CSES - Intersection Points | Giao điểm

Xem PDF



Tác giả:
Dạng bài
Đ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\)\(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


  • 0
    nguyen_ducminh 1:30 a.m. 16 Tháng 9, 2023 đã chỉnh sửa

    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

    • Dòng đầu tiên gồm số nguyên \(n\) (\(1 \leq n \leq 10^5\)) - số đoạn thẳng.
    • Trong \(n\) dòng tiếp theo, mỗi dòng gồm 4 số nguyên \(x_1\), \(y_1\), \(x_2\)\(y_2\) với ý nghĩa đoạn thẳng nối từ điểm \((x_1,y_1)\) đến điểm \((x_2,y_2)\) thỏa mãn các điều kiện: \(-10^6 \leq x_1 \leq x_2 \leq 10^6\), \(-10^6 \leq y_1 \leq y_2 \leq 10^6\), và \((x_1,y_1) \neq (x_2,y_2)\).

    Output

    • In ra số giao điểm.

    Test 1

    Input
    3
    2 3 7 3
    3 1 3 5
    6 2 6 6
    Output
    2