Problem: Consider a house plan. 

Let the house be represented by an infinite horizontal strip defined by the inequality  - h ≤ y ≤ h. Strictly outside the house there are two light sources at the points (0, f) and (0, - f). Windows are located in the walls, the windows are represented by segments on the lines y = h and y = - h. Also, the windows are arranged symmetrically about the line y = 0.

Your task is to find the area of the floor at the home, which will be lighted by the sources of light. 

<image>

Input

The first line of the input file contains three integers n, h and f (1 ≤ n ≤ 500, 1 ≤ h ≤ 10, h < f ≤ 1000). Next, n lines contain two integers each li, ri ( - 5000 ≤ li < ri ≤ 5000), each entry indicates two segments. Endpoints of the first segment are (li, h)-(ri, h), and endpoints of the second segment are (li, - h)-(ri, - h). These segments describe location of windows. Numbers in the lines are space-separated. It is guaranteed that no two distinct segments have common points. 

Output

Print the single real number — the area of the illuminated part of the floor with an absolute or relative error of no more than 10 - 4.

Examples

Input

1 1 2
-1 1


Output

10.0000000000


Input

2 2 4
-1 0
1 2


Output

23.3333333333

Note

The second sample test is shown on the figure. Green area is the desired area of the illuminated part of the floor. Violet segments indicate windows.

Solution (in JAVA):

Solution:
import java.util.*;
import static java.lang.Math.*;

public class E {
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		N = in.nextInt();
		H = in.nextInt();
		F = in.nextInt();
		e1 = new Point(0, F);
		e2 = new Point(0, -F);
		L1 = new Line[2*N];
		L2 = new Line[2*N];
		double minx = Long.MAX_VALUE;
		for(int i = 0; i < N;i++){
			int l = in.nextInt();
			int r = in.nextInt();
			L1[2*i] = new Line(new Point(l, H), new Point(l*(F+H)/(F-H), -H));
			L1[2*i+1] = new Line(new Point(r, H), new Point(r*(F+H)/(F-H), -H));
			L2[2*i] = new Line(new Point(l*(F+H)/(F-H), H), new Point(l, -H));
			L2[2*i+1] = new Line(new Point(r*(F+H)/(F-H), H), new Point(r, -H));
			minx = min(minx, L1[2*i].b.x);
			minx = min(minx, L1[2*i+1].b.x);
		}
		double area = 0;
		for(int i = 0; i < N*2;i++){
			int sign = i%2 == 0 ? -1 : 1;
			area += 2*sign*((L1[i].a.x+L1[i].b.x)/2)*2*H;
		}
		for(int i = 0; i < N*2; i++){
			int sign2 = i%2 == 0 ? -1 : 1;

			double overlap = 0.0;
			for(int j = 0; j < N*2; j++){
				int sign1 = j%2 == 0 ? -1 : 1;
				Point inter = segseg(L2[i], L1[j]);
				if(inter != null && !EQ(inter.y, -H) && !EQ(inter.y, H)){
					if(L2[i].a.x < L1[j].a.x){ //L2 on top
						overlap += sign1*((L2[i].a.x+inter.x)/2)*(H-inter.y);
						overlap += sign1*((L1[j].b.x+inter.x)/2)*(H+inter.y);
					}else{ // L1 on top
						overlap += sign1*((L1[j].a.x+inter.x)/2)*(H-inter.y);
						overlap += sign1*((L2[i].b.x+inter.x)/2)*(H+inter.y);
					}
				}else{
					double mid2 = (L2[i].a.x+L2[i].b.x)/2;
					double mid1 = (L1[j].a.x+L1[j].b.x)/2;
					if(mid2 < mid1){ // on left
						overlap += sign1*((L2[i].a.x+L2[i].b.x)/2)*2*H;;
					}else{ // on right
						overlap += sign1*((L1[j].a.x+L1[j].b.x)/2)*2*H;;
					}
				}
			}
			area -= sign2*overlap;
		}
		System.out.format("%.09f\n", area);
	}
	static int N;
	static double H, F;
	static Point e1, e2;
	static Line[] L1, L2; //even => minus, odd => plus










	static double eps = 1e-9;
	static boolean EQ(double a, double b){return abs(a-b) < eps;}
	static double SQ(double d){return d*d;}
	static double normang(double t){ return ((t % (2*PI)) + 2*PI) % (2*PI); }
	static double angdiff(double t1, double t2){ return normang(t1 - t2 + PI) - PI; }
	static ArrayList<Point> makeVec(Point...P){
		ArrayList<Point> ans = new ArrayList<Point>();
		for(Point p:P)
			ans.add(p);
		return ans;
	}
	static class Point{
		double x, y;
		public Point(double x, double y){this.x = x;this.y = y;}
		Point add(Point p){return new Point(x+p.x, y+p.y);}
		Point sub(Point p){return new Point(x-p.x, y-p.y);}
		Point mult(double d){return new Point(x*d, y*d);}
		double dot(Point p){return x*p.x+ y*p.y;}
		double cross(Point p){return x*p.y - y*p.x;}
		double len(){return hypot(x, y);}
		Point scale(double d){return mult(d/len());}
		double dist(Point p){return sub(p).len();}
		double ang(){return atan2(y, x);}
		static Point polar(double r, double theta){return new Point(r*cos(theta), r*sin(theta));}
		Point rot(double theta){return new Point(x*cos(theta)-y*sin(theta), x*sin(theta)+y*cos(theta));}
		Point perp(){return new Point(-y, x);}
		boolean equals(Point p){return EQ(0, dist(p));}
		double norm(){return dot(this);}
		public String toString(){return String.format("(%.03f, %.03f)", x, y);}
	}	
	static class Line{
		Point a, b;
		Line(Point a, Point b){this.a = a;this.b = b;}
		public String toString(){return String.format("{%s -> %s}", a, b);}
	}
	static class Circle{
		Point p;double r;
		public Circle(Point p, double r){this.p = p;this.r = r;}
		public Circle(Point a, Point b, Point c){
			Point p1 = a.add(b).mult(0.5);
			Line l1 = new Line(p1, p1.add(a.sub(b).perp()));
			Point p2 = b.add(c).mult(0.5);
			Line l2 = new Line(p2, p2.add(b.sub(c).perp()));
			p = lineline(l1, l2);
			assert(p != null);
			r = p.dist(a);
		}
	}
	static double ccw(Point p1, Point p2, Point p3){
		return p2.sub(p1).cross(p3.sub(p1));
	}
	static Point lineline(Line a, Line b){
		double d = a.b.sub(a.a).cross(b.b.sub(b.a));
		if(EQ(d, 0))
			return null;
		return a.a.add((a.b.sub(a.a)).mult(b.b.sub(b.a).cross(a.a.sub(b.a))/d));
	}
	static Point segline(Line a, Line b){
		Point inter = lineline(a, b);
		if(inter == null || !onseg(a, inter))
			return null;
		return inter;
	}
	static Point segseg(Line a, Line b){
		Point inter = lineline(a, b);
		if(inter == null || !onseg(a, inter) || !onseg(b, inter))
			return null;
		return inter;
	}
	static boolean onseg(Line l, Point p){
		return p.dist(l.a) + p.dist(l.b) < l.a.dist(l.b) + eps;
	}
	static boolean online(Line l, Point p){
		return EQ(ccw(l.a, l.b, p), 0);
	}

	static Point pointline(Point p, Line l){
		Point v = l.b.sub(l.a).scale(1);
		double dot = p.sub(l.a).dot(v);
		return l.a.add(v.mult(dot));
	}
	static Point pointseg(Point p, Line l){
		Point v = l.b.sub(l.a).scale(1);
		double dot = p.sub(l.a).dot(v);
		dot = max(dot, 0);
		dot = min(dot, l.b.dist(l.a));
		return l.a.add(v.mult(dot));
	}
	static double pointsegdist(Point p, Line l){
		return pointseg(p, l).dist(p);
	}
	static double pointlinedist(Point p, Line l){
		return pointline(p, l).dist(p);
	}

	static double polyarea(Point[] poly){
		double area = 0;
		for(int i = 0; i < poly.length; i++)
			area += poly[i].cross(poly[(i+1)%poly.length]);
		return abs(area)/2.0;
	}
	static int pointinpoly(Point[] poly, Point p){
		double ang = 0.0;
		for(int i = 0; i < poly.length; i++){
			Point a = poly[i];
			Point b = poly[(i+1)%poly.length];
			if(onseg(new Line(a, b), p))
				return 0;
			ang += angdiff(a.sub(p).ang(), b.sub(p).ang());
		}
		return EQ(ang, 0) ? -1 : 1;
	}

	static Point v0;
	static ArrayList<Point> convexhull(ArrayList<Point> P){//tested
		v0 = null;
		for(Point p:P)
			if(v0 == null || p.x < v0.x - eps || (EQ(p.x, v0.x) && p.y < v0.y))
				v0 = p;
		Collections.sort(P, new Comparator<Point>(){
			public int compare(Point a, Point b){
				if(a == v0) return -1;
				if(b == v0) return 1;
				double ccw = ccw(v0, a, b);
				if(EQ(ccw, 0)){
					double d1 = v0.dist(a);
					double d2 = v0.dist(b);
					if(d1 < d2) return -1;
					if(d1 > d2) return 1;
					return 0;
				}
				return (int) -signum(ccw);
			}});
		ArrayList<Point> ch = new ArrayList<Point>();
		for(Point p:P){
			while(ch.size() >= 2 && ccw(ch.get(ch.size()-2), ch.get(ch.size()-1), p) <= 0)
				ch.remove(ch.size()-1);
			ch.add(p);
		}
		return ch;
	}
	//add half space intersection

	//circle
	static ArrayList<Point> circline(Circle c, Line l){
		Point x = pointline(c.p, l);
		double d = x.dist(c.p);
		if(d > c.r + eps) return new ArrayList<Point>();
		double h = sqrt(SQ(c.r) - SQ(d));
		Point v = x.sub(c.p);
		return makeVec(c.p.add(v.scale(d)).add(v.scale(h)), c.p.add(v.scale(d)).add(v.scale(-h)));
	}
	static ArrayList<Point> circcirc(Circle a, Circle b){
		double d = a.p.dist(b.p);
		if(d > a.r + b.r + eps) return new ArrayList<Point>();
		if(d < abs(a.r - b.r) - eps) return new ArrayList<Point>();
		double x = (SQ(d) - SQ(b.r) + SQ(a.r)) / 2*d;
		double y = sqrt(SQ(a.r) - SQ(x));
		Point v = b.p.sub(a.p);
		return makeVec(a.p.add(v.scale(x)).add(v.perp().scale(y)), a.p.add(v.scale(x)).add(v.perp().scale(-y)));
	}
	static ArrayList<Line> circcirctan(Circle a, Circle b){//tested
		if(a.r < b.r)
			return circcirctan(b, a);
		ArrayList<Line> res = new ArrayList<Line>();
		double d = a.p.dist(b.p);
		double d1 = a.r*d/(a.r + b.r);
		double t = acos(a.r/d1);
		Point v = b.p.sub(a.p);
		res.add(new Line(a.p.add(v.scale(a.r).rot(t)), b.p.add(v.scale(-b.r).rot(t))));
		res.add(new Line(a.p.add(v.scale(a.r).rot(-t)), b.p.add(v.scale(-b.r).rot(-t))));   
		t = asin((a.r-b.r)/d)+PI/2;
		v = a.p.sub(b.p);
		res.add(new Line(a.p.add(v.scale(a.r).rot(t)), b.p.add(v.scale(b.r).rot(t))));
		res.add(new Line(a.p.add(v.scale(a.r).rot(-t)), b.p.add(v.scale(b.r).rot(-t)))); 
		return res;
	}

	//3d
	static class Point3{
		double x, y, z;
		Point3(double x, double y, double z) {  this.x = x; this.y = y; this.z = z; }
		static Point3 sphere(double theta, double phi, double r){
			return new Point3(r*cos(theta)*sin(phi),r*sin(theta)*sin(phi),r*cos(theta));
		}
		double[] ang(){ return new double[]{atan(y/x), acos(z/len())}; }
		Point proj(){ return new Point(x, y); }
		Point3 add(Point3 p){ return new Point3(x+p.x, y+p.y, z+p.z); }
		Point3 sub(Point3 p){ return new Point3(x-p.x, y-p.y, z-p.z); }
		double dot(Point3 p){ return x*p.x+ y*p.y+ z*p.z; }
		Point3 cross(Point3 p){ return new Point3(y*p.z-p.y*z, z*p.x-p.z*x, x*p.y-p.x*y); }
		Point3 mult(double d){ return new Point3(x*d, y*d, z*d); }
		double len(){ return sqrt(x*x+y*y+z*z); }
		Point3 scale(double d){ return mult(d/len()); }
		double dist(Point3 p){ return sub(p).len(); } 
		boolean equals(Point3 p){ return EQ(dist(p), 0); }
	}
	static Point3[] getbasis(Point3 z){
		z = z.scale(1);
		Point3 t = new Point3(1, 0, 0);
		Point3 y = z.cross(t);
		if(EQ(y.len(), 0)){
			t = new Point3(0, 1, 0);
			y = z.cross(t);
		}
		Point3 x = y.cross(z);
		assert(x.cross(y).equals(z));
		return new Point3[]{x, y, z};
	}
	static Point3 trans(Point3[] B, Point3 p){
		return new Point3(B[0].dot(p), B[1].dot(p), B[2].dot(p));
	}
	static Point3 invtrans(Point3[] B, Point3 p){
		return B[0].mult(p.x).add(B[1].mult(p.y)).add(B[2].mult(p.z));
	}
}