ICPC NEERC 2012 C - Caravan Robbers - Olympiads Online Judge

ICPC NEERC 2012 C - Caravan Robbers

Points: 10

Time limit: 2.0s

Memory limit: 1G

Problem type

Long long ago in a far far away land, there were two great cities and The Great Caravan Road between them. Many robber gangs "worked" on that road.

By an old custom, the $i$ $i$ -th band robbed all merchants that dared to travel between $a_i$ $a_{i}$ and $b_i$ $b_{i}$ miles of The Great Caravan Road. The custom was old, but a clever one, as there were no two distinct $i$ $i$ and $j$ $j$ such that $a_i \le a_j$ $a_{i} \leq a_{j}$ and $b_j \le b_i$ $b_{j} \leq b_{i}$ . Still, when intervals controlled by two gangs intersected, bloody fights erupted occasionally. Gang leaders decided to end those wars. They decided to assign each gang a new interval such that all new intervals do not intersect (to avoid bloodshed), for each gang their new interval is subinterval of the old one (to respect the old custom), and all new intervals are of equal length (to keep things fair).

You are hired to compute the maximal possible length of an interval that each gang would control after redistribution.

Input

The first line contains $n$ $n$ $(1 \le n \le 100\,000)$ $(1 \leq n \leq 100 000)$ – the number of gangs. Each of the next $n$ $n$ lines contains information about one of the gangs – two integer numbers $a_i$ $a_{i}$ and $b_i$ $b_{i}$ $(0 \le a_i < b_i \le 1\,000\,000)$ $(0 \leq a_{i} < b_{i} \leq 1 000 000)$ . Data provided in the input file conforms to the conditions laid out in the problem statement.

Output

Output the maximal possible length of an interval in miles as an irreducible fraction $p/q$ $p / q$ .

Sample Input

Copy

Sample Output

Copy

5/2

Sample Explanation

In the above example, one possible set of new intervals that each gang would control after redistribution is given below.

The first gang would control an interval between $7/2 = 3.5$ $7 / 2 = 3.5$ and $12/2 = 6$ $12 / 2 = 6$ miles which has length of $5/2$ $5 / 2$ and is a subinterval of its original $(2, 6)$ $(2, 6)$ .
The second gang would control an interval between $2/2 = 1$ $2 / 2 = 1$ and $7/2 = 3.5$ $7 / 2 = 3.5$ miles which has length of $5/2$ $5 / 2$ and is a subinterval of its original $(1, 4)$ $(1, 4)$ .
The third gang would control an interval between $16/2 = 8$ $16 / 2 = 8$ and $21/2 = 10.5$ $21 / 2 = 10.5$ miles which has length of $5/2$ $5 / 2$ and is a subinterval of its original $(8, 12)$ $(8, 12)$ .

Comments

1

JFerraro8 commented on Jan. 20, 2024, 5:31 p.m. ← edit 5 →

The intervals are such that no two gangs have the same start or end point, which means the intervals are distinct for each gang. However, the intervals may overlap partially. That is, part of one gang's interval may lie within the bounds of another's, which has led to conflicts.

The statement "no two distinct i, j....." means that you won't find a situation where one gang's interval is completely within the bounds of another's. But it doesn't rule out partial overlaps.

Note: ^^JUST A SELF REMINDER to avoid reading the instructions every time

1

dnialh_ commented on Jan. 21, 2024, 1:13 a.m. ← edited →

If there were no partial overlaps in the input then there would be no need for redistribution.