Glass cutting
InterviewTime limit1sMemory limit1024 MB
Given an M by N pane with K point defects, find the largest axis-parallel rectangle that has no defect strictly inside it.
- Level
Medium5 of 10
- Topics
- Sorting, Brute force, Array
- Solved
- No attempts yet
Statement
Artūras built a frame for a new greenhouse and plans to glaze it. He bought a glass pane of size (length , width ), but at home he found defects in it. All defects are small, so treat each one as a point where the glass is slightly cracked.
Artūras does not want to use poor-quality glass, so he plans to cut out the largest possible rectangle from the pane that contains no defects.
Artūras has a device that holds the pane and makes straight cuts parallel to its edges, that is, horizontal and vertical cuts. The device is precise enough that a cut can pass through a defect without the glass breaking.
Compute the maximum area of a defect-free rectangle that Artūras can cut from the pane.
A defect may lie on the edge of the cut rectangle, but no defect may lie inside it.
Input
The first line contains three integers , , and . Each of the next lines contains two integers and , the coordinates of one defect.
The lower left corner of the original pane has coordinates , and the upper right corner has coordinates .
It is always true that and . All defect coordinates are distinct.
Output
Print one integer: the maximum area of a defect-free rectangle that Artūras can cut from the pane.
Constraints
,