1, Problem description

There are n closed intervals D1,..., Dn on the number axis. The interval Di is described by a pair of integers [ai, bi], which satisfies AI < Bi. It is known that the sum of the lengths of these intervals is at least 10000. Therefore, by appropriately moving these intervals, you can always make their "union" cover [010000] - that is, every point in the interval [0,10000] falls in at least one interval. You want to find a moving method to minimize the displacement in the interval with the largest displacement difference. Specifically, suppose you move Di to [ai+ci,bi+ci]. You want to minimize maxi|ci|.

2, Input format

• The first line of input contains an integer n, which represents the number of intervals.
• Next, there are n lines, 2 integers ai,bi in each line, separated by a space, representing the interval [ai,bi]. Ensure that the sum of the length of the interval is at least 10000.

3, Output format

Output a number indicating the answer. If the answer is an integer, only the integer part is output. If the answer is not an integer, the output is rounded to one decimal place.

4, Sample

• Sample input 1
  2
  10 5010
  4980 9980
• sample output
  20
• Example description
  The first section moves 10 to the left; The second section moves 20 to the right.
  
  
• Sample input 2
  4
  0 4000
  3000 5000
  5001 8000
  7000 10000
• sample output
  0.5
• Example description
  The second interval moves to the right by 0.5; The third interval can be moved to the left by 0.5.

5, Data scale and agreement

• For 30% of the evaluation cases, 1 ≤ n ≤ 10;
• For 100% evaluation cases, 1 ≤ n ≤ 10000, 0 ≤ AI < Bi ≤ 10000.
• Time limit: 1.5s
• Memory limit: 256.0MB

6, Problem solving ideas and methods

According to the meaning of the question, it is easy to think that a possible minimum displacement can be specified first, and the maximum displacement of each section can not exceed the specified displacement. If all sections can be covered after translation [010000], then this specified displacement is desirable.
There are two key issues:
1. How to find the minimum displacement
2. Judge whether this displacement can make all sections cover [010000] after translation

• For the first problem, a stupid method is to traverse the specified displacement from 1. Once it is feasible, then this value is the desired value. Observe the example. The translation may be 0.5. Therefore, multiply the size of the whole interval by 2 to ensure that the translation is an integer. Obviously, this method is likely to lead to timeout, and the worst time complexity is O (20000). Therefore, according to keywords such as interval and minimum value, it can be associated with dichotomy, and the worst time complexity is O (log2 (20000)). The implementation of dichotomy is relatively simple. The termination condition is that the left end point between the two partitions is greater than the right end point.
• For the second problem, the method adopted is to arrange the intervals in ascending order according to the right end point (the reason why the right end point is used is because it covers the interval from left to right according to the general idea, so the right end point closer to the right will be used later to ensure the minimum displacement), and then merge the intervals from left to right in turn. The specific method is to use a k to maintain the left end point of [020000] this interval, specify the maximum displacement of each interval as X, and then traverse each interval arranged in ascending order according to the right end point, Once the displacement x is satisfied, the interval can cover the value of k (this is very important. If k cannot be covered, this interval does not contribute to covering the whole interval in the current situation, but it may be useful later. Therefore, if you use up a qualified interval, throw an interval, and then traverse the interval from the beginning, depending on the code implementation), update the value of k (i.e. interval merging). Finally, if k is not less than 20000, it indicates that the specified x satisfies the condition. Then you can use X to continue dichotomy.

There are two situations for updating, as follows:

• Case 1
  
  It can be found that the current interval can cover k after translation. Obviously, in order to make the following translation as few as possible, fill this interval with more positions as much as possible. It can be found that a+x is still larger than K. therefore, the whole interval can be merged to the right of K, so K becomes k+(b-a) (note that b-a does not need to add 1 here because K needs to be covered.)
• Case 2
  
  In this case, the current interval can also cover k after translation, but a+x is smaller than k, and this interval can only be translated to the position of a+x at most. Therefore, K at this time is updated with b+x.

Reference codes are as follows:

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;


public class Main {
	static ArrayList<Node> array=new ArrayList<Node>();
	static class Node{
		int a,b;
		public Node(int a,int b) {
			this.a=a;
			this.b=b;
		}
	}
	static class Cmp implements Comparator<Node>{
		@Override
		public int compare(Node a,Node b) {
			return a.b-b.b;//Right boundary ascending sort
		}
	}
	static boolean check(int x) {
		int k=0,maxnum=20000;
		ArrayList<Node> tmp=new ArrayList<Node>();
		for (int i = 0; i < array.size(); i++) {
			tmp.add(array.get(i));
		}
		//System.out.println(array.size());
		while (true) {
			boolean found = false;
			for(int i=0;i<tmp.size();i++)
			{
				Node now = tmp.get(i);
				int ta = now.a;
				int tb = now.b;
				if(ta-x<=k && tb+x>=k)
				{
					found = true;
					int len = tb-ta;
					if(ta+x>=k) k += len;
					else k = tb+x;
					tmp.remove(i);
					break;
				}
			}
			if(!found || k>=maxnum) break;		
		}
		//System.out.println(k);
		return k>=maxnum;//When the whole interval is covered, it returns true
	}
	public static void main(String[] args) {
		Scanner cScanner=new Scanner(System.in);
		int n=cScanner.nextInt();
		for (int i = 0; i < n; i++) {
			int a=cScanner.nextInt()*2;
			int b=cScanner.nextInt()*2;
			array.add(new Node(a, b));
		}
		array.sort(new Cmp());
		int l=0,r=20001;
		int ans=0;
		while (l<=r) {
			int mid = (l+r)/2;
			if (check(mid)) {
				r = mid-1;
				ans = mid;
			}
			else {
				l=mid+1;
			}
		}
		if (ans%2==0) {
			System.out.println(ans/2);
		}
		else {
			System.out.println(ans/2.0);
		}
	}
}