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 | ecnerwala | 3649 |

2 | Benq | 3581 |

3 | orzdevinwang | 3570 |

4 | Geothermal | 3569 |

4 | cnnfls_csy | 3569 |

6 | tourist | 3565 |

7 | maroonrk | 3531 |

8 | Radewoosh | 3521 |

9 | Um_nik | 3482 |

10 | jiangly | 3468 |

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

1 | maomao90 | 174 |

2 | awoo | 164 |

3 | adamant | 162 |

4 | TheScrasse | 159 |

5 | nor | 158 |

6 | maroonrk | 156 |

7 | -is-this-fft- | 151 |

8 | SecondThread | 147 |

9 | orz | 146 |

10 | pajenegod | 145 |

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-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/25/2024 07:08:16 (i1).

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.