Blankets
Time limit1sMemory limit128 MB
Compute the average pairwise overlap area of n identical axis-aligned rectangles from their corner positions.
- Level
Medium7 of 10
- Topics
- Segment tree, Sorting, Geometry, Math
- Solved
- No attempts yet
Problem
This summer the citizens of Byteburg are streaming down to the city beach on Byteotian Lake to sunbathe. Everyone who comes brings a blanket made by Byteasar & Son, the label everybody wants this season. The blankets differ only in their patterns, all of them measure , and everyone spreads a blanket so that its longer side is perpendicular to the lake.
Professor Byteoni is one of this year's sunbathers. After a few days on the beach he noticed that every person spreads the blanket on one favourite spot, always the same one. People arrive and leave at different hours, yet the professor has never heard of anyone taking over somebody else's spot. He decided to study the phenomenon himself.
He set up a coordinate system on the beach and wrote down, for each of the citizens, the spot where that person always spreads the blanket. The OX axis is parallel to the sides of length and the OY axis to the sides of length , so citizen covers the rectangle whose lower left corner is .
The professor first wanted the overlap area of every pair of blankets. Then he realised that the average of those values is all his research needs. Compute the expected overlap area of the blankets of two different citizens picked at random, where each of the unordered pairs is equally likely.
Input
The first line has three integers , and : the number of citizens and the two side lengths of a blanket (, ).
Each of the next lines has two integers and , the coordinates of the spot where citizen always puts the lower left corner of the blanket ().
Output
Print the expected overlap area on one line as an irreducible fraction: the numerator, one slash, the denominator, with no spaces, in the form p/q. Reduce it so that and , and print the denominator even when it equals . If no two blankets overlap, the expected value is and the answer is 0/1. The numerator does not always fit in a signed 64-bit integer.
Hint

The picture shows the arrangement of the first example. The six pairs overlap in areas , , , , , , so the expected value is .