Codeforces and Polygon may be unavailable from May 23, 4:00 (UTC) to May 23, 7:00 (UTC) due to technical maintenance. ×

A simple geometry problem based on intersection of rectangles.

Revision en2, by saketag007, 2019-11-04 15:03:18

I was given 'n' rectangles represented by their diagonals on a 2-d plane. Then i would be asked multiple queries , in which i would be given an integer 'x' and i was asked to find the number of integer coordinates in the intersection regions of exactly 'x' rectangles. Suppose q = 4 , then i have to find the number of integer co-ordinates in the intersection region of exactly 4 rectangles . The rectangles could be in the form of a cluster so there could be more than one group of 4 rectangles , in that case i should return the sum of number of integer coordinates of all that intersections.

Constraints:-

Number of Rectangles — 0<n<10^5

Number of Queries — 0<n<10^5

Any tips would be helpful.

Tags #geometry, line intersections

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English saketag007 2019-11-04 15:03:18 8
en1 English saketag007 2019-11-04 15:02:39 774 Initial revision (published)