Problem: You are given two circles. Find the area of their intersection.

Input

The first line contains three integers x1, y1, r1 ( - 109 ≤ x1, y1 ≤ 109, 1 ≤ r1 ≤ 109) — the position of the center and the radius of the first circle.

The second line contains three integers x2, y2, r2 ( - 109 ≤ x2, y2 ≤ 109, 1 ≤ r2 ≤ 109) — the position of the center and the radius of the second circle.

Output

Print the area of the intersection of the circles. The answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6.

Examples

Input

0 0 4
6 0 4


Output

7.25298806364175601379


Input

0 0 5
11 0 5


Output

0.00000000000000000000

Solution (in JAVA):

Solution:

import java.awt.geom.Point2D;
import java.math.BigDecimal;
import java.math.MathContext;
import java.util.Scanner;

public class Edu2d {
	static MathContext mc = new MathContext(50);
	public static void main(String[] args) {
		try (Scanner scan = new Scanner(System.in)) {
			Point2D.Double a = new Point2D.Double(scan.nextDouble(), scan.nextDouble());
			double r1 = scan.nextInt();
			Point2D.Double b = new Point2D.Double(scan.nextDouble(), scan.nextDouble());
			double r2 = scan.nextInt();
			
			double ans = 0.0;
			if (a.distance(b)>= r1+r2){System.out.println(ans);return;}
			if (r1 < r2 && a.distance(b)+r1 <= r2){
				System.out.println(r1*r1*Math.PI);
				return;
			}
			if (r2 < r1 && a.distance(b)+r2 <= r1){
				System.out.println(r2*r2*Math.PI);
				return;
			}
			if (a.equals(b)&&r1==r2){
				System.out.println(r1*r1*Math.PI);
				return;
			}
			
			if(r2 < r1){
			    // swap
				double temp = r1;
			    r1 = r2;
			    r2 = temp;
			}
			int error = 200;
			BigDecimal r = new BigDecimal(r1), R = new BigDecimal(r2), d = distance(a,b),
					   rr = r.multiply(r,mc), RR = R.multiply(R, mc), dd = d.multiply(d, mc);
			
			
			BigDecimal ONE = arccos((((dd.add(rr,mc)).subtract(RR,mc)).divide(((d.add(d,mc)).multiply(r,mc)),mc)),error);
			BigDecimal TWO = arccos((((dd.add(RR,mc)).subtract(rr,mc)).divide(((d.add(d,mc)).multiply(R,mc)),mc)),error);
			
			BigDecimal p1 = (ONE.multiply(rr,mc)).subtract(new BigDecimal(.5).multiply(rr,mc).multiply(sine(ONE.multiply(new BigDecimal(2.0),mc),error),mc),mc);
			BigDecimal p2 = (TWO.multiply(RR,mc)).subtract(new BigDecimal(.5).multiply(RR,mc).multiply(sine(TWO.multiply(new BigDecimal(2.0),mc),error),mc),mc);
			System.out.println((p1.add(p2)));
		}
	}
	
	private static BigDecimal distance(Point2D.Double p, Point2D.Double q) {
		BigDecimal x1 = new BigDecimal(p.x), y1 = new BigDecimal(p.y),
				   x2 = new BigDecimal(q.x), y2 = new BigDecimal(q.y);
		
		BigDecimal diffXsqr = (x1.subtract(x2,mc)).pow(2, mc);
		BigDecimal diffYsqr = (y1.subtract(y2,mc)).pow(2, mc);
		
		BigDecimal ans = diffXsqr.add(diffYsqr,mc);
		ans = sqrt(ans);
		
		return ans;
	}
	
	static BigDecimal sine(BigDecimal X, int precision) {
		if (precision>1000)precision=1000;

		while (X.compareTo(new BigDecimal(Math.PI*2.0)) >= 0)X = X.subtract(new BigDecimal(Math.PI*2.0), mc);
		
		BigDecimal num = BigDecimal.ONE;
		BigDecimal fact = BigDecimal.ONE;
		BigDecimal sum = BigDecimal.ZERO;
		for (int i=0;i<=precision;i++){
			
			BigDecimal pow = X.pow(2*i+1,mc);
			if (i!=0)
				fact = fact.multiply(new BigDecimal(2*i+1,mc).multiply(new BigDecimal(2*i),mc),mc);
			sum = sum.add( (num.multiply(pow, mc)).divide(fact, mc),mc);
			num = num.negate();
		}
		
		return sum;
	}
	
	static BigDecimal cosine(BigDecimal X, int precision) {
		if (precision>1000) precision = 1000;
		X = (X.remainder(new BigDecimal(2*Math.PI,mc), mc));
		BigDecimal negative = BigDecimal.ONE;
		BigDecimal fact = BigDecimal.ONE;
		BigDecimal sum  = BigDecimal.ZERO;
		for (int K = 0; K < precision; K++) {
			BigDecimal numer = X.pow(2*K,mc);
			if (K!=0)
				fact = fact.multiply(new BigDecimal(2*K),mc).multiply(new BigDecimal(2*K-1),mc);
			sum = sum.add((negative.multiply(numer,mc)).divide(fact,mc),mc);
			negative = negative.negate();
		}
		
		return sum;
	}
	
	static BigDecimal arccos(BigDecimal X, int precision) {
		
		BigDecimal lo = new BigDecimal(Math.PI,mc);
		BigDecimal hi = BigDecimal.ZERO;
		
		int ops = 0;
		BigDecimal ans = null;
		BigDecimal cos = null;
		while (ops<100){
			
			ans = (lo.add(hi,mc)).divide(new BigDecimal(2.0,mc),mc);
			cos = cosine(ans, precision);
			
			if (X.compareTo(cos) < 0) hi = ans;
			else if (X.compareTo(cos) > 0) lo = ans;
			else break;
			
			ops++;
		}
		return ans;
	}

	
	static BigDecimal sqrt(BigDecimal X)
	{
		BigDecimal S = X;
		for(int rep = 0;rep < 1000;rep++){
			S = S.subtract(S.multiply(S, mc).subtract(X,mc).divide(BigDecimal.valueOf(2).multiply(S,mc), mc));
		}
		return S;
	}
}