Problem: One

Problem Statement

A beautiful mountain range can be seen from the train window.
The window is a rectangle with the coordinates of the lower left corner (0, 0) and the coordinates of the upper right corner (W, H).
N peaks can be seen from the window, and the i-th peak has the shape of an upwardly convex parabola y = a_i (x-p_i) ^ 2 + q_i.
Find the length of the boundary between the mountain and the sky.

The following three figures correspond to Sample Input. The part shown by the thick line is the boundary between the mountain and the sky.

<image> <image> <image>

Constraints

* 1 ≤ W, H ≤ 100
* 1 ≤ N ≤ 50
* -100 ≤ a_i ≤ -1
* 0 ≤ p_i ≤ W
* 1 ≤ q_i ≤ H
* If i \ neq j, then (a_i, p_i, q_i) \ neq (a_j, p_j, q_j)

Input

Input follows the following format. All given numbers are integers.


W H N
a_1 p_1 q_1
...
a_N p_N q_N

Output

Output the length of the boundary between the mountain and the sky on one line.
The output value must have an absolute or relative error of less than 10 ^ {-6} with the true value.

Examples

Input

20 20 1
-1 10 10


Output

21.520346288593280


Input

20 20 2
-1 10 10
-2 10 5


Output

21.520346288593280


Input

15 100 2
-2 5 100
-2 10 100


Output

126.921542730127873

Solution (in JAVA):

Solution:
import java.util.*;
import java.awt.geom.*;

public class Main{
	double EPS = 1.0e-08;
	TreeSet<Double> list;

	private void doit(){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int w = sc.nextInt();
			int h = sc.nextInt();
			int n = sc.nextInt();
			int [][] f = new int[n][3]; // {a,b,c}
			for(int i = 0; i < n; i++){
				int a = sc.nextInt();
				int p = sc.nextInt();
				int q = sc.nextInt();
				f[i][0] = a;
				f[i][1] = -2 * p * a;
				f[i][2] = p * p * a + q;
			}
			list = new TreeSet<Double>();
			for(int i = 0; i < n; i++){
				
				//yama yama
				for(int j = i + 1; j < n;j++){
					calcX(f[i], f[j]);
				}
				
				//yama mado
				double [] xWhenY0 = calcXByF(f[i][0], f[i][1], f[i][2]);
				for(int j = 0; j < xWhenY0.length; j++){
					list.add(xWhenY0[j]);
				}
				
				double [] xWhenYh = calcXByF(f[i][0], f[i][1], f[i][2] - h);
				for(int j = 0; j < xWhenYh.length; j++){
					list.add(xWhenYh[j]);
				}
			}
			list.add(0.0);
			list.add((double) w);
			ArrayList<Double> intersectionP = new ArrayList<Double>();
			
			for(double value: list){
				if(value < 0 || value > w){
				}
				else{
					intersectionP.add(value);
				}
			}
			
			double sum = 0;
			for(int i = 1; i < intersectionP.size(); i++){
				double rangeA = intersectionP.get(i-1);
				double rangeB = intersectionP.get(i);
				double rangeMid = (rangeA + rangeB) / 2;
				
				int ind = -1;
				double max = -1 * Integer.MIN_VALUE;
				for(int j = 0; j < n; j++){
					double nowY = calcFx(f[j], rangeMid);
					if(nowY > max){
						max = nowY;
						ind = j;
					}
				}
				
				if(max < 0 || max > h) continue;
				
				
				
				//simpson
				double nowsum = 0;
				//DAME
				//nowsum = ((rangeB - rangeA) / 6) * (calcF(f[ind], rangeA) + 4 * calcF(f[ind], rangeMid) + calcF(f[ind], rangeB));
				
				int separatesize = 10000;
				double deltaX = (rangeB - rangeA) / (2 * separatesize);
				nowsum = calcF(f[ind], rangeA) + 4.0 * calcF(f[ind], rangeA + deltaX) + calcF(f[ind], rangeB);
				
				for(int j = 1; j < separatesize; j++){
					nowsum += 2.0 * calcF(f[ind],rangeA + 2 * j * deltaX) + 
							4.0 * calcF(f[ind], rangeA + (2 * j + 1) * deltaX);
				}
				nowsum = deltaX * nowsum / 3.0;
				sum += nowsum;
			}
			System.out.printf("%.15f\n", sum);
		}
	}

	private double calcF(int[] f, double range) {
		double a = 2 * f[0] * range;
		double b = f[1];
		double sq = 1 + (a + b) * (a + b);
		return Math.sqrt(sq);
	}

	private void calcX(int [] f1, int [] f2) {
		int [] f3 = new int[3];
		for(int i = 0; i < 3; i++){
			f3[i] = f1[i] - f2[i];
		}
		double [] x = calcXByF(f3[0], f3[1], f3[2]);
		for(int i = 0; i < x.length; i++){
			list.add(x[i]);
		}
	}

	private double calcFx(int [] f, double resx) {
		double res = f[0] * resx * resx + f[1] * resx + f[2];
		return res;
	}

	private double[] calcXByF(int a, int b, int c) {
		if(a == 0){
			return new double[]{-1.0 * c / b};
		}
		
		int d = b * b - 4 * a * c;
		if(d < 0){
			return new double[]{};
		}
		else if(d == 0){
			return new double[]{(-1 * b) / (2 * a)};
		}
		else{
			double sqrt = Math.sqrt(d);
			double res1 = (-1 * b + sqrt) / (2 * a);
			double res2 = (-1 * b - sqrt) / (2 * a);
			return new double []{res1, res2};
		}
	}

	private void debug(Object... o) {
		System.out.println("debug = " + Arrays.deepToString(o));
	}

	public static void main(String[] args) {
		new Main().doit();
	}
}