1028C.md (1696B)
1 Source: https://codeforces.com/problemset/problem/1028/C 2 3 C. Rectangles 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 Find any point with integer coordinates that belongs to at least $(n-1)$ given rectangles. 24 25 Input 26 27 The first line contains a single integer $n$ ($2 \le n \le 132\,674$) — the number of given rectangles. 28 29 Each the next $n$ lines contains four integers $x_1$, $y_1$, $x_2$ and $y_2$ ($-10^9 \le x_1 \lt x_2 \le 10^9$, $-10^9 \le y_1 \lt y_2 \le 10^9$) — the coordinates of the bottom left and upper right corners of a rectangle. 30 31 Output 32 33 Print two integers $x$ and $y$ — the coordinates of any point that belongs to at least $(n-1)$ given rectangles. 34 35 Examples 36 37 Input 38 39 ``` 40 3 41 0 0 1 1 42 1 1 2 2 43 3 0 4 1 44 ``` 45 46 Output 47 48 ``` 49 1 1 50 ``` 51 52 Input 53 54 ``` 55 3 56 0 0 1 1 57 0 1 1 2 58 1 0 2 1 59 ``` 60 61 Output 62 63 ``` 64 1 1 65 ``` 66 67 Input 68 69 ``` 70 4 71 0 0 5 5 72 0 0 4 4 73 1 1 4 4 74 1 1 4 4 75 ``` 76 77 Output 78 79 ``` 80 1 1 81 ``` 82 83 Input 84 85 ``` 86 5 87 0 0 10 8 88 1 2 6 7 89 2 3 5 6 90 3 4 4 5 91 8 1 9 2 92 ``` 93 94 Output 95 96 ``` 97 3 4 98 ``` 99 100 Note 101 102 The picture below shows the rectangles in the first and second samples. The possible answers are highlighted. 103 104  105 106 The picture below shows the rectangles in the third and fourth samples. 107 108 