eolymp
bolt
Try our new interface for solving problems
Problems

Wedding Hall

Wedding Hall

Kamran has recently bought a rectangular flat garden in an awesome part of the countryside. His business plan is to construct a Hall to host wedding ceremonies, since the countryside has recently attracted a lot of attention for being a fantastic area to host wedding ceremonies. As women and men sections must be separated based on the nation law, he thinks of designing the hall in three sections: men section, women section and common section (including rest rooms, dinner room and etc). As the common section must be easily accessible to all persons, it must be designated in the middle of the other two sections. Among several proposal designs, Kamran has selected the one depicted below where all three sections are squares of the same size, they are attached to each other like an \textbf{L} shape, their sides are parallel to the garden sides, and the visible sides of the common section from outside face the south and west of the garden. Now the main question is where the hall must be constructed. The garden is full of old trees and cutting the trees is forbidden due to high air pollution. He kindly asks you to help him to find the largest hall that he can construct. \includegraphics{https://static.e-olymp.com/content/94/941d4bd6202e917b5cca3104983f350e886fbaad.jpg} \InputFile There are multiple test cases in the input. Each test case starts with a line containing a non-negative integers \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{50000}) and two positive integers \textbf{a} and \textbf{b} (all not exceeding \textbf{1000000}) where \textbf{n} is the number of distinct trees in the garden and \textbf{a} and \textbf{b} specify the sides of the garden. Precisely, \textbf{\[0, a\]}×\textbf{\[0, b\]} denotes the rectangle modeling the garden. The next \textbf{n} lines, each contains \textbf{2} space-separated non-negative integers \textbf{x_i} and \textbf{y_i} (\textbf{0} < \textbf{x_i} < \textbf{a}, \textbf{0} < \textbf{y_i} < \textbf{b}) denoting the\textbf{x} and \textbf{y} coordinates of a tree, respectively. You may assume that trees have distinct coordinates and the south side (i.e. \textbf{\[0, a\]}) and the west side (i.e. \textbf{\[0, b\]}) of the garden lie on the \textbf{x}-axis and the \textbf{y}-axis, respectively. The input terminates with a line containing "\textbf{0 0 0}" which should not be processed. \OutputFile For each test case, output the area of the largest hall that Kamran can construct in his garden. Note that the hall can touch the trees or the garden sides but it can’t interiorly include them. The output must be rounded to "exactly" two digits after the decimal point.
Time limit 1 second
Memory limit 64 MiB
Input example #1
2 3 5
2 2
1 4
0 0 0
Output example #1
6.75
Source 38th ACM International Collegiate Programming Contest, 2013–2014 Asia Region, Tehran Site, Sharif University of Technology, 19–20 December 2013