| # | User | Rating |
|---|---|---|
| 1 | tourist | 3803 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3627 |
| 4 | ecnerwala | 3584 |
| 5 | orzdevinwang | 3573 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | Radewoosh | 3542 |
| 9 | jqdai0815 | 3532 |
| 10 | gyh20 | 3447 |
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 165 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | maroonrk | 152 |
| 5 | -is-this-fft- | 151 |
| 5 | nor | 151 |
| 7 | atcoder_official | 147 |
| 8 | TheScrasse | 146 |
| 9 | Petr | 145 |
| 10 | SecondThread | 142 |
You are given a list of coordinates that represent the bottom left and top right coordinates of the rectangle. You have to find a line parallel to the y-axis which will divide all the rectangles into 2 equal halves.
Overlapping is allowed....
I gave an approach but interviewer didn't seem convinced. Can you guys share any approaches?
A line which divides a rectangle into 2 equal halves must pass through its centre. Take the centre of any one rectangle and choose the line parallel to y-axis passing through this point, if the centre of all other rectangles also lie on this line then this line is the answer to divide all rectangles in 2 equal halves otherwise no solution is possible.
I think he meant a line that breaks the rectangles into two sets, one set where each rectangle is to the left of this line, and another set where each rectangle is to the right of it.
Sorry, my bad. I guess you are kind of right now that I think about it.
So, here's my new solution: Sort the rectangles based on their right corner's x coordinate. Then iterate from left to right until you collect n/2 rectangles, if the next rectangle in the list is not overlapping with the n/2th rectangle we chose then the required line is "x=[value of right corner's x coordinate of n/2th chosen rectangle]", otherwise no solution is possible. What about this aproach.
I gave a similar approach but it seemed interviewer had something else in mind. He told that this won't work and did not even give me the case where
Don't worry bro, Trust in your knowledge and all the best for future interviews.
can you try doing something like take the min x coord and max x coord , take the average of it and then check how many are on either side , whichever side has lesser amount of rectangle you shift your x coord such that it accomodates atleast one rectangle to the lesser side. something like binary serach maybe. you also can precalculate if my x is at a particular coordinate how many are going to be on either side
Discrete the rectangles, put them into segment trees, and brute force to get the answer. It's an $$$\Theta(n\log n)$$$ approach.
Can you please elaborate on this ?
OMG, I don't know how to explain it in English... I have a Chinese blog (OI-Wiki). Maybe you can look at the gif (which scans parallel to the x-axis) or translate it using ChatGPT.
Click me
What is the answer when there are only 2 rectangles and they overlap?
Can my (answer) line goes through the rectangles?
yes , the line can go through the reactangles
wait, if I'm not wrong the questions wants us to create a line which divide the same amount (not size/area nor proportion) of rectangles into two areas (left and right).
if I put a vertical line through a rectangle does that mean left and right get +1 each or +0.5 each or something else?
also about my previous question, since I'm not clear yet. What is the answer when there are only 2 rectangles and they overlap?
input format:
x1 y1 x2 y2example:
-2 0 1 3
-5 0 2 7
where do I put my vertical line (answer)?
Treat rectangles as segments and find intersection of all n segments. If the line cant pass through the border of a rectangle just dont count borders as part of the intersection. UPD: This is wrong, I didnt understand the problem correctly
If I have understood the problem correctly, then I think Binary search on answer would help.
Find the sum of the area of the rectangles upto x = mid, then accordingly changing the mid to get the answer.
Either the bool function that you talked about could be simple O(n). But what if we can optimize that too? Sum of areas of rectangles upto mid will require some precomputation (prefix sum) with sorting and some math too since the line x=mid could pass right through some rectangles, could we achieve that?
I don't fully understand the problem but here's my two cents,
find the center of each rectangle on the X-axis: x = ( x1 + x2 )/2
if the Xs are the same , then the line passes through the point (x,0) since it's parallel to the Y-axis, if not, then no solution exists.
ok
Ok
Ok
Ok