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 CPP):

Solution:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <complex>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <iterator>

using namespace std;

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define iter(c) __typeof__((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

const int INFTY=1<<29;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

struct Point{
	double x,y;
	Point(){}
	Point(double x,double y):x(x),y(y){}
	bool operator<(const Point& p)const{
		return x<p.x || (x==p.x && y<p.y);
	}
};
ostream& operator<<(ostream& os,const Point& p)
{
	printf("(%.2f,%.2f)",p.x+EPS,p.y+EPS);
	return os;
}

// f(x)=a*(x-p)^2+q
double f(double a,double p,double q,double x)
{
	return a*(x-p)*(x-p)+q;
}

// \int{sqrt(1+x^2) dx}
double integral(double x)
{
	return (x*sqrt(1+x*x)+log(x+sqrt(1+x*x)))/2;
}
// \int{sqrt(1+(2a(x-p))^2)}
double integral(double a,double p,double x)
{
	return integral(2*a*(x-p))/(2*a);
}
// y=a(x-p)^2の[x1,x2]間の曲線長
double curvelen(double a,double p,double x1,double x2)
{
	return integral(a,p,x2)-integral(a,p,x1);
}

int main()
{
	int w,h,n; cin>>w>>h>>n;
	vi as(n),ps(n),qs(n);
	rep(i,n) cin>>as[i]>>ps[i]>>qs[i];
	
	vector<Point> cs; // 交点
	cs.emplace_back(0,0);
	cs.emplace_back(w,0);
	
	rep(i,n){
		double a=as[i];
		double b=-2*as[i]*ps[i];
		double c=as[i]*ps[i]*ps[i]+qs[i];
		
		cs.emplace_back(0,f(as[i],ps[i],qs[i],0)); // 左枠との交点
		cs.emplace_back(w,f(as[i],ps[i],qs[i],w)); // 右枠との交点
		
		double x1=(-b-sqrt(b*b-4*a*c))/(2*a);
		double x2=(-b+sqrt(b*b-4*a*c))/(2*a);
		cs.emplace_back(x1,f(as[i],ps[i],qs[i],x1)); // 下枠との交点1
		cs.emplace_back(x2,f(as[i],ps[i],qs[i],x2)); // 下枠との交点2
	}
	
	rep(i,n) rep(j,n){ // 2つの放物線の交点
		// ax^2+bx+c=0をxについて解く
		double a=as[j]-as[i];
		double b=-2*(as[j]*ps[j]-as[i]*ps[i]);
		double c=(as[j]*ps[j]*ps[j]+qs[j])-(as[i]*ps[i]*ps[i]+qs[i]);
		
		if(abs(a)<EPS){
			if(abs(b)>EPS){
				double x=-c/b;
				if(EPS<x && x<w-EPS)
					cs.emplace_back(x,f(as[i],ps[i],qs[i],x));
			}
		}
		else{
			double d=b*b-4*a*c;
			if(abs(d)<EPS){ // 1点で交わる
				double x=-b/(2*a);
				cs.emplace_back(x,f(as[i],ps[i],qs[i],x));
			}
			else if(d>EPS){ // 2点で交わる
				double x1=(-b-sqrt(b*b-4*a*c))/(2*a);
				double x2=(-b+sqrt(b*b-4*a*c))/(2*a);
				cs.emplace_back(x1,f(as[i],ps[i],qs[i],x1));
				cs.emplace_back(x2,f(as[i],ps[i],qs[i],x2));
			}
		}
	}
	
	sort(all(cs));
	for(int i=0;i<cs.size();){
		if(cs[i].x<-EPS || w+EPS<cs[i].x)
			cs.erase(cs.begin()+i);
		else
			i++;
	}
	for(int i=0;i+1<cs.size();){
		if(cs[i].x+EPS>cs[i+1].x)
			cs.erase(cs.begin()+i);
		else
			i++;
	}
	
	double res=0;
	rep(i,cs.size()-1){
		int j=-1;
		rep(k,n){
			double y1=f(as[k],ps[k],qs[k],cs[i].x);
			double y2=f(as[k],ps[k],qs[k],cs[i+1].x);
			double y3=f(as[k],ps[k],qs[k],(cs[i].x+cs[i+1].x)/2);
			if(j==-1 && y3>EPS
			|| j!=-1 && y3>f(as[j],ps[j],qs[j],(cs[i].x+cs[i+1].x)/2)+EPS)
				j=k;
		}
		if(j!=-1)
			res+=curvelen(as[j],ps[j],cs[i].x,cs[i+1].x);
	}
	printf("%.10f\n",res);
	
	return 0;
}