Mạng Lưới Cáp Xung Đột
Points
55
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
number
Đề 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
YESnếu có ít nhất một cặp đoạn thẳng cắt nhau, ngược lại in raNO.
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
Community Discussion