codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/e47a869e382d2295eeb08173b4b637ceb9c1520d.png) 
    105 
    106 The picture below shows the rectangles in the third and fourth samples.
    107 
    108  ![](https://espresso.codeforces.com/bff8ead23110ce820ca90a087d0cf0031aa73067.png)