305415: CF1028C. Rectangles

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Rectangles

题意翻译

### 题目大意 在平面直角坐标系中给定$n$个矩形,要求找到一个点$(x,y)$,这个点在至少$n-1$个给定矩形的内部或边界 ### 输入格式 第一行一个整数$n$,表示矩形个数 下面$n$行每行$4$个整数$x1,y1,x2,y2$,表示矩形的左下和右上坐标 ### 输出格式 两个整数$x,y$

题目描述

You are given $ n $ rectangles on a plane with coordinates of their bottom left and upper right points. Some $ (n-1) $ of the given $ n $ rectangles have some common point. A point belongs to a rectangle if this point is strictly inside the rectangle or belongs to its boundary. Find any point with integer coordinates that belongs to at least $ (n-1) $ given rectangles.

输入输出格式

输入格式


The first line contains a single integer $ n $ ( $ 2 \le n \le 132\,674 $ ) — the number of given rectangles. Each the next $ n $ lines contains four integers $ x_1 $ , $ y_1 $ , $ x_2 $ and $ y_2 $ ( $ -10^9 \le x_1 < x_2 \le 10^9 $ , $ -10^9 \le y_1 < y_2 \le 10^9 $ ) — the coordinates of the bottom left and upper right corners of a rectangle.

输出格式


Print two integers $ x $ and $ y $ — the coordinates of any point that belongs to at least $ (n-1) $ given rectangles.

输入输出样例

输入样例 #1

3
0 0 1 1
1 1 2 2
3 0 4 1

输出样例 #1

1 1

输入样例 #2

3
0 0 1 1
0 1 1 2
1 0 2 1

输出样例 #2

1 1

输入样例 #3

4
0 0 5 5
0 0 4 4
1 1 4 4
1 1 4 4

输出样例 #3

1 1

输入样例 #4

5
0 0 10 8
1 2 6 7
2 3 5 6
3 4 4 5
8 1 9 2

输出样例 #4

3 4

说明

The picture below shows the rectangles in the first and second samples. The possible answers are highlighted. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1028C/afe32198a5a9eb1ff9e8a20f68bff3bd1db43611.png)The picture below shows the rectangles in the third and fourth samples. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1028C/1f383f98b80a1cee6f760c4ae11ccf4d5b79e3ad.png)

Input

题意翻译

### 题目大意 在平面直角坐标系中给定$n$个矩形,要求找到一个点$(x,y)$,这个点在至少$n-1$个给定矩形的内部或边界 ### 输入格式 第一行一个整数$n$,表示矩形个数 下面$n$行每行$4$个整数$x1,y1,x2,y2$,表示矩形的左下和右上坐标 ### 输出格式 两个整数$x,y$

加入题单

上一题 下一题 算法标签: