Tin học trẻ 2023 - Chung kết - Tìm điểm
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Cho ~n + 1~ hình chữ nhật trên mặt phẳng ~Oxy~, các hình chữ nhật đều có các cạnh song song hoặc vuông góc với trục tọa độ. Hãy tìm điểm ~(x,y)~ nằm trong ít nhất ~n~ hình chữ nhật đã cho. Điểm ~(x,y)~ được gọi là nằm trong hình chữ nhật xác định bởi hai điểm ~(x_1,y_1)~ và ~(x_2,y_2)~ nếu:
~\min(x_1,x_2) \le x \le \max(x_1,x_2)~;
~\min(y_1,y_2) \le y \le \max(y_1,y_2)~.
Input
Dòng đầu chứa số nguyên ~n~ ~(1 \le n \le 2 \cdot 10^5)~;
~n + 1~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên ~x_1, y_1, x_2, y_2~ ~(0 \le x_1, x_2, y_1, y_2 \le 10^9)~ mô tả hai điểm ~(x_1,y_1)~ và ~(x_2,y_2)~ là hai góc của hình chữ nhật, dữ liệu đảm bảo hai điểm này là phân biệt.
Output
Hai số nguyên ~x, y~ là tọa độ của điểm nằm trong ít nhất ~n~ hình chữ nhật, nếu có nhiều điểm thỏa mãn thì đưa ra điểm có ~x~ nhỏ nhất, nếu có nhiều điểm thỏa mãn có cùng ~x~ nhỏ nhất thì đưa ra điểm có ~y~ nhỏ nhất. Nếu không có điểm nào thỏa mãn chỉ ghi -1.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~25~ | ~x_1, x_2, y_1, y_2 \le 20~ |
| 2 | ~25~ | ~x_1, x_2, y_1, y_2 \le 2000~ |
| 3 | ~25~ | ~n \le 2000~ |
| 4 | ~25~ | Không có ràng buộc gì thêm |
Sample Input 1
2
1 1 2 3
2 2 3 1
3 6 0 4
Sample Output 1
2 1
Bình luận