Tin học trẻ 2023 - Chung kết - Tìm điểm

Xem dạng PDF

Gửi bài giải

Điểm: 25,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong 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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.