Problem: Problem F: Magnum Tornado

We have a toy that consists of a small racing circuit and a tiny car. For simplicity you can regard the circuit as a 2-dimensional closed loop, made of line segments and circular arcs. The circuit has no branchings. All segments and arcs are connected smoothly, i.e. there are no sharp corners.

The car travels on this circuit with one distinct feature: it is capable of jumping, which enables short cuts. It can jump at any time for any distance. The constraints are that 1) the traveling direction will never change during each jump, 2) the jumping direction needs to match the traveling direction at the time of take-off, and 3) the car must land on the circuit in parallel to the tangent at the landing point. Note that, however, the traveling direction at the landing point may be the opposite of the forward direction (we define forward direction as the direction from the starting point to the ending point of each line segment in the circuit.) That is, the car can traverse part of the circuit in the reverse direction.

Your job is to write a program which, given the shape of the circuit, calculates the per-lap length of the shortest route. You can ignore the height of the jump, i.e. just project the route onto the plane on which the circuit resides. The car must start from the starting point of the first line segment, heading towards the ending point of that segment, and must come back to the same starting point heading in the same direction.

Figure 1 shows the solution for the first sample input.

<image>
Figure 1: The solution for the first sample input



Input

The input begins with a line that solely consists of an integer N (2 <= N <= 100), the number of line segments in the circuit. This is followed by N lines, where the i-th line corresponds to the i-th line segment (1 <= i <= N). Each of these N lines contains 4 integers x0, y0, x1 and y1 (-100 <= x0, y0, x1, y1 <= 100) in this order, separated by a space. Here (x0, y0) is the starting point and (x1, y1) is the ending point of the i-th line segment. For each i, the i-th and (i+1)-th line segments are connected smoothly by a circular arc, which you may assume exists uniquely (for simplicity, we consider the (N+1)-th line as the 1st line). You may also assume that, while two line segments or circular arcs may cross each other, they will never overlap nor be tangent to each other.

Output

For each test case, output one line that solely consists of a decimal value, representing the per-lap length. The output value should be in a decimal fraction and should not contain an error greater than 0.001.

Examples

Input

5
0 1 0 2
1 3 2 3
2 2 1 2
1 1 2 1
2 0 1 0


Output

9.712


Input

12
4 5 4 6
3 7 1 7
0 8 0 10
1 11 3 11
4 10 4 9
5 8 99 8
100 7 100 4
99 3 4 3
3 2 3 1
2 0 1 0
0 1 0 3
1 4 3 4


Output

27.406

Solution (in CPP):

Solution:
#include <cstdio>
#include <iostream>
#include <cmath>
#include <complex>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <queue>
#include <cfloat>
#include <functional>
#include <cassert>
using namespace std;

#define EPS 1e-8

typedef double D;
typedef complex<D> P;
typedef const P &rP;
typedef vector<D> vD;
typedef pair<D,int> pdi;

const D pi = acos(-1.0);
const P iu(0.0, 1.0);

D dot(rP a, rP b){
	return real(a) * real(b) + imag(a) * imag(b);
}

D cross(rP a, rP b){
	return real(a) * imag(b) - imag(a) * real(b);
}

P intersect(rP a, rP va, rP b, rP vb){
	P vab = b - a;
	D t = cross(vb, vab) / cross(vb, va);
	return a + t * va;
}

vD comtang(rP c1, D r1, P c2, D r2, bool out){
	vD ret;
	c2 -= c1;
	if(norm(c2) > EPS){
		D sgn = (out ? -1.0 : 1.0);
		D s = (r1 + sgn * r2) / abs(c2);
		if(abs(s) < 1.0 + EPS){
			if(s > 1.0){ s = 1.0; }
			else if(s < -1.0){ s = -1.0; }
			D a = arg(c2), b = asin(s) - 0.5 * pi;
			ret.resize(2);
			ret[0] = a - b;
			ret[1] = a + b;
		}
	}
	return ret;
}

struct comparer{
	bool operator() (D x, D y) const{
		return x < y - EPS;
	}
};

struct arcinfo{
	P cen;
	D rd, af, al;
	map<D,int,comparer> mp;

	arcinfo(rP p1, rP p2, rP p3, rP p4){
		P va = p2 - p1, vb = p4 - p3;
		if(abs(cross(va, vb)) < EPS){
			cen = 0.5 * (p2 + p3);
		}
		else{
			cen = intersect(p2, va * iu, p3, vb * iu);
		}
		rd = abs(p2 - cen);

		af = arg(p2 - cen);
		al = arg(p3 - cen);
		if(cross(va, cen - p2) < 0.0){
			swap(af, al);
		}
		af += 8.0 * pi;
		while(al < af){ al += 2.0 * pi; }
	}

	bool check(D &a) const{
		while(a < af - EPS){ a += 2.0 * pi; }
		if(a > al + EPS){ return false; }
		if(a < af){ a = af; }
		if(a > al){ a = al; }
		return true;
	}
	
	P point(double a) const{
		return cen + polar(rd, a);
	}
};

struct edgeinfo{
	int f, t;
	D len;
};

vector<arcinfo> arcs;
int V;

int getid(int t, D a){
	if(!arcs[t].mp.count(a)){
		arcs[t].mp[a] = V;
		V += 2;
	}
	return arcs[t].mp[a];
}


int main(){
	int n;
	vector<P> pts;
	double x, y;
	scanf("%d", &n);
	for(int i = 0; i < 2 * n; ++i){
		scanf("%lf%lf", &x, &y);
		pts.push_back(P(x, y));
	}

	arcs.reserve(n);
	int k = 2 * n - 2;
	for(int i = 0; i < 2 * n; i += 2){
		arcs.push_back(arcinfo(pts[k], pts[k+1], pts[i], pts[i+1]));
		k = i;
	}

	vector<edgeinfo> E;
	for(int i = 0; i < arcs.size(); ++i)
	for(int j = i + 1; j < arcs.size(); ++j){
		vD ret = comtang(arcs[i].cen, arcs[i].rd, arcs[j].cen, arcs[j].rd, true);
		for(k = 0; k < ret.size(); ++k){
			D a = ret[k], b = ret[k];
			if(arcs[i].check(a) && arcs[j].check(b)){
				int ia = getid(i, a), ib = getid(j, b);
				P pa = arcs[i].point(a), pb = arcs[j].point(b);
				D ds = abs(pa - pb);

				if(cross(pa - arcs[i].cen, pb - pa) < 0.0){
					swap(ia, ib);
				}

				E.push_back((edgeinfo){ia, ib, ds});
				E.push_back((edgeinfo){ib + 1, ia + 1, ds});
			}
		}

		ret = comtang(arcs[i].cen, arcs[i].rd, arcs[j].cen, arcs[j].rd, false);
		for(k = 0; k < ret.size(); ++k){
			D a = ret[k], b = ret[k] + pi;
			if(arcs[i].check(a) && arcs[j].check(b)){
				int ia = getid(i, a), ib = getid(j, b);
				P pa = arcs[i].point(a), pb = arcs[j].point(b);
				D ds = abs(pa - pb);
				if(cross(pa - arcs[i].cen, pb - pa) > 0.0){
					E.push_back((edgeinfo){ia, ib + 1, ds});
					E.push_back((edgeinfo){ib, ia + 1, ds});
				}
				else{
					E.push_back((edgeinfo){ia + 1, ib, ds});
					E.push_back((edgeinfo){ib + 1, ia, ds});
				}
			}
		}
	}


	for(int i = 0; i < arcs.size(); ++i){
		assert(!arcs[i].mp.empty());
		map<D,int,comparer>::iterator it1, it2;
		it1 = arcs[i].mp.begin();
		while(1){
			it2 = it1;
			if(++it1 == arcs[i].mp.end()){ break; }
			int a = it1->second, b = it2->second;
			D ds = arcs[i].rd * abs(it1->first - it2->first);
			E.push_back((edgeinfo){b, a, ds});
			E.push_back((edgeinfo){a + 1, b + 1, ds});
		}
	}

	vector<vector<pdi> > G(V);
	for(int i = 0; i < E.size(); ++i){
		G[E[i].f].push_back(pdi(E[i].len, E[i].t));
	}

	D stang = arg(pts[0] - arcs[0].cen);
	arcs[0].check(stang);
	assert(arcs[0].mp.count(stang));
	int start = arcs[0].mp[stang];

	vD dst(V, DBL_MAX);
	priority_queue<pdi,vector<pdi>,greater<pdi> > pq;
	for(int i = 0; i < G[start].size(); ++i){
		int t = G[start][i].second;
		D d = G[start][i].first;
		dst[t] = d;
		pq.push(pdi(d, t));
	}

	while(!pq.empty()){
		pdi p = pq.top();
		pq.pop();
		if(dst[p.second] != p.first){ continue; }
		if(p.second == start){
			printf("%f\n", p.first);
			return 0;
		}

		for(int i = 0; i < G[p.second].size(); ++i){
			D d = G[p.second][i].first + p.first;
			int t = G[p.second][i].second;
			if(dst[t] > d){
				dst[t] = d;
				pq.push(pdi(d, t));
			}
		}
	}

	fprintf(stderr, "no answer\n");
}