Hello everyone. Today i meet a problem like find the intersection areas of n rectangles. i use IT tree but i can't not solve with case have a area that more than 3 rectangles intersection. Very thanks you help me to solve this proplem.

# | User | Rating |
---|---|---|

1 | Radewoosh | 3759 |

2 | orzdevinwang | 3697 |

3 | jiangly | 3662 |

4 | Benq | 3644 |

5 | -0.5 | 3545 |

6 | ecnerwala | 3505 |

7 | tourist | 3486 |

8 | inaFSTream | 3478 |

9 | maroonrk | 3454 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 173 |

2 | awoo | 168 |

3 | nor | 164 |

4 | SecondThread | 163 |

5 | BledDest | 162 |

5 | Um_nik | 162 |

7 | maroonrk | 161 |

8 | -is-this-fft- | 150 |

9 | Geothermal | 146 |

10 | TheScrasse | 143 |

Hello everyone. Today i meet a problem like find the intersection areas of n rectangles. i use IT tree but i can't not solve with case have a area that more than 3 rectangles intersection. Very thanks you help me to solve this proplem.

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/05/2023 02:11:03 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Intersection of two rectangles is a rectangle. I don't think any further explanation is really necessary. A bit of casework and the problem is done.

Good luck!

Hmm sorry when my question is not clear. It mean you have n rectangles, you find the intersection areas of n rectangles.

By mentioning IT tree, which I suppose is segment tree, I think you realized this problem can be solved with sweep line and range queries. A classic problem would be to find

unionof $$$n$$$ rectangles instead ofintersection. If you know how to solve for union, I think you can also solve for intersection.