Problem F
The Sultan’s Problem
Input: Standard Input
Output: Standard Output
Once upon a time, there lived a great sultan, who was very much fond of his wife. He wanted to build a Tajmahal for his wife (ya, our sultan idolized Mughal emperor Shahjahan). But alas, due to budget cuts, loans, dues and many many things, he had no fund to build something so big. So, he decided to build a beautiful garden, inside his palace.
The garden is a rectangular piece of land. All the palace’s water lines run through the garden, thus, dividing it into pieces of varying shapes. He wanted to cover each piece of the land with flowers of same kind.
Figure 1
The figure above shows a sample flower garden. All the lines are straight lines, with two end points on two different edge of the rectangle. Each piece of the garden is covered with the same kind of flowers.
The garden has a small fountain, located at position (x,y). You can assume that, it is not on any of the lines. He wants to fill that piece with her favourite flower. So, he asks you to find the area of that piece.
Input
Input contains around 500 test cases. Each case starts with 5 integers, N, W, H, x, y, the number of lines, width and height of the garden and the location of the fountain. Next N lines each contain 4 integers, x1 y1 x2 y2, the two end points of the line. The end points are always on the boundary of the garden. You can assume that, the fountain is not located on any line.
Output
For each test case, output the case number, with the area of the piece covered with her favourite flower.
Constraints
- 1 ≤ W, H ≤ 200,000
- 1 ≤ N ≤ 500
|
Sample Input |
Sample Output |
|
3 100 100 20 30 0 0 100 100 100 0 0 100 0 40 40 100 |
Case #1: 1780.00000 |
Problemsetter: Manzurur Rahman Khan
Special Thanks To: Mohammad Mahmudur Rahman