Mạng Lưới Cáp Xung Đột

Buổi 61 — Hình học tính toán
Points
55
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Một bản thiết kế mạch in gồm $N$ đường dẫn là các đoạn thẳng trên mặt phẳng. Hai đường dẫn xung đột nếu chúng cắt nhau (có ít nhất một điểm chung, kể cả chạm đầu mút hoặc trùng nhau một phần).

Sử dụng thuật toán đường quét (Sweep Line - Shamos-Hoey), hãy kiểm tra xem trong $N$ đoạn thẳng đã cho có tồn tại ít nhất một cặp đoạn thẳng xung đột nhau hay không.

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 $4$ số nguyên $x_1, y_1, x_2, y_2$ mô tả một đoạn thẳng.
Dữ liệu ra
  • In ra YES nếu có ít nhất một cặp đoạn thẳng cắt nhau, ngược lại in ra NO.
Ví dụ
Input Output
3
0 0 4 4
0 4 4 0
5 0 5 5
YES
Giới hạn
  • $1 \le N \le 10^5$
  • $|x|, |y| \le 10^9$
  • Thời gian: 3 giây
  • Bộ nhớ: 256 MB
Draft saved