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
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <unordered_map>
#include <iterator>
#include <assert.h>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);}
template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);}

namespace geom{
#define X real()
#define Y imag()
#define at(i) ((*this)[i])
#define SELF (*this)
	enum {TRUE = 1, FALSE = 0, BORDER = -1};
	typedef int BOOL;
	typedef double R;
	const R INF = 1e8;
	const R EPS = 1e-8;
	const R PI = 3.1415926535897932384626;
	inline int sig(const R &x) { return (abs(x) < EPS ? 0 : x > 0 ? 1 : -1); }
	inline BOOL less(const R &x, const R &y) {return sig(x-y) ? x < y : BORDER;}
	typedef complex<R> P;
	inline R norm(const P &p){return p.X*p.X+p.Y*p.Y;}
	inline R inp(const P& a, const P& b){return (conj(a)*b).X;}
	inline R outp(const P& a, const P& b){return (conj(a)*b).Y;}
	inline P unit(const P& p){return p/abs(p);}
	inline P proj(const P &s, const P &t){return t*inp(s, t)/norm(t);}
	inline int ccw(const P &s, const P &t, const P &p, int adv=0){
		int res = sig(outp(t-s, p-s));
		if(res || !adv) return res;
		if(sig(inp(t-s, p-s)) < 0) return -2;	// p-s-t
		if(sig(inp(s-t, p-t)) < 0) return 2;	// s-t-p
		return 0;								// s-p-t
	}
	
	
	struct L : public vector<P>{	// line
		L(const P &p1, const P &p2){this->push_back(p1);this->push_back(p2);}
		L(){}
		P dir()const {return at(1) - at(0);}
		BOOL online(const P &p)const {return !sig(outp(p-at(0), dir()));}
	};
	struct S : public L{	// segment
		S(const P &p1, const P &p2):L(p1, p2){}
		S(){}
		BOOL online(const P &p)const {
			if(!sig(norm(p - at(0))) || !sig(norm(p - at(1)))) return BORDER;
			return !sig(abs(at(0)-p) + abs(at(1) - p) - abs(at(0) - at(1)));
		}
	};
	struct C : public P{
		C(){}
		C(const P& p, const R r):P(p), r(r){}
		R r;
		BOOL inside(const P& p)const { return less(norm(p-SELF), r*r);}
	};
	struct F : public C{
		R s, t;
		int cc;
		F(const C &c, R ss, R tt, int cc=1):C(c), s(ss), t(tt),cc(cc){
			if(PI < s) s -= 2*PI;
			if(PI < t) t -= 2*PI;
		}
		R length(){
			return ((t < s) ? t - (s-2*PI) : t-s) * r;
		}
		BOOL inside(const P& p)const {
			P v = p - SELF;
			R a = arg(v);
			if(t < s){
				return less(s, a) || less(a, t);
			}else{
				return less(s, a) && less(a, t);
			}
		}
	};

	inline P proj(const P &s, const L &t){return t[0] + proj(s-t[0], t[1]-t[0]);}
	inline P crosspoint(const L &l, const L &m){
		R A = outp(l.dir(), m.dir()), B = outp(l.dir(), l[1] - m[0]);
		if(!sig(abs(A)) && !sig(abs(B))) return m[0]; // same line
		if(abs(A) < EPS) assert(false); // !!!PRECONDITION NOT SATISFIED!!!
		return m[0] + B / A * (m[1] - m[0]);
	}
	vector<L> CommonTangent(C c1, C c2){
		if(c1.r > c2.r) swap(c1, c2);
		double d = abs(c1-c2);
		vector<L> res;
		if(d < EPS) return res;
		if(d + EPS > c1.r + c2.r){
			// テ・ツ??ヲツ篠・テァツキツ?
			P crs = (c1*c2.r + c2*c1.r) / (c1.r + c2.r);
			double rad = asin(c1.r/abs(crs-c1));
			res.push_back(L(crs, crs + (c1-crs)*polar(1., rad)));
			res.push_back(L(crs, crs + (c1-crs)*polar(1., -rad)));
		}
		if(c1.r + d + EPS > c2.r){
			// テ・ツ、ツ姪ヲツ篠・テァツキツ?
			double rad = 0.5*PI+asin((c2.r-c1.r) / d);
			P v = unit(c2-c1)*polar(1., rad);
			if(c1.r + d - EPS < c2.r){
				res.push_back(L(c1+v*c1.r, c1+v*c1.r+(c1-c2)*P(0, 1)));
			}else{
				res.push_back(L(c1+v*c1.r, c2+v*c2.r));
				v = 2.*proj(v, c2-c1) - v;
				res.push_back(L(c1+v*c1.r, c2+v*c2.r));
			}
		}
		return res;
	}

#undef SELF
#undef at
}

using namespace geom;


namespace std{
	bool operator<(const P &a, const P &b){return abs(a.X-b.X) > EPS ? a.X < b.X : a.Y+EPS < b.Y;}
	bool operator==(const P &a, const P &b){return !sig(norm(a-b));}
	istream& operator>>(istream &is, P &p){R x,y;is>>x>>y;p=P(x, y);return is;}
	istream& operator>>(istream &is, L &l){l.resize(2);return is >> l[0] >> l[1];}
	istream& operator>>(istream &is, C &c){return is >> (P &)c >> c.r;}
}

int n;

R dijkstra(const vector< vector<pair<int, R>> > &g, int start){
	int n = g.size();
	vector<R> ret(n, INF);
	priority_queue<pair<R, int>, vector<pair<R, int>>, greater<pair<R, int>> > dp;
	dp.push(pair<R, int>(0., start));
	while(!dp.empty()){
		int s = dp.top().second;
		R c = dp.top().first;
		dp.pop();
		if(s == start && c != 0) return c;
		if(s != start && ret[s] < c - EPS) continue;
		FOR(it, g[s]){
			int t = it->first;
			if(ret[t] - EPS > c+it->second){
				ret[t] = c+it->second;
				dp.push(pair<R, int>(ret[t], t));
			}
		}
	}
	return INF;
}


int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	vector<pair<pair<P, P>, double>> e;
	vector<P> p;
	P fst, prev;
	vector<S> s(n);
	REP(i, n)cin >> s[i];
	vector<F> f;
	REP(i, n){
		const S &cur = s[i];
		const S &nxt = s[(i+1) % n];
		C c;
		(P&)c = sig(outp(cur.dir(), nxt.dir())) ? 
			   crosspoint(L(cur[1], cur[1]+cur.dir()*P(0, 1)), L(nxt[0], nxt[0]+nxt.dir()*P(0, 1)))
			: (cur[1] + nxt[0]) * .5;
		c.r = abs(cur[1] - c);
		R ca = arg(cur[1] - c);
		R cb = arg(nxt[0] - c);
		int cc = ccw(cur[0], cur[1], c);
		if(cc == -1) swap(ca, cb);
		f.emplace_back(c, ca, cb, cc);
		p.push_back(cur[0]);
		p.push_back(cur[1]);
		p.push_back(cur[0]+P(1000, 0));
		p.push_back(cur[1]+P(1000, 0));
		e.emplace_back(mp(cur[0], cur[1]), abs(cur.dir()));
		e.emplace_back(mp(cur[1]+P(1000, 0), cur[0]+P(1000, 0)), abs(cur.dir()));
		e.emplace_back(mp(cur[1], nxt[0]), f.back().length());
	}
	REP(i, n)REP(j, n)if(i!=j){
		const F &u = f[i];
		const F &v = f[j];
		vector<L> ls = CommonTangent(u, v);
		FOR(s, ls){
			S root(proj(u, *s), proj(v, *s));
			if(!u.inside(root[0]) || !v.inside(root[1])) continue;
			int f1 = ccw(root[0], root[1], u) != u.cc;
			int f2 = ccw(root[0], root[1], v) != v.cc;
			p.push_back(root[0]);
			p.push_back(root[1]);
			p.push_back(root[0]+P(1000, 0));
			p.push_back(root[1]+P(1000, 0));
			e.emplace_back(mp(root[0]+(f1?P(1000, 0):P(0,0)), 
							  root[1]+(f2?P(1000, 0):P(0,0))), abs(root.dir()));
			e.emplace_back(mp(root[1]+(!f2?P(1000, 0):P(0,0)), 
							  root[0]+(!f1?P(1000, 0):P(0,0))), abs(root.dir()));
		}
	}
	sort(ALL(p));UNIQUE(p);
	
	REP(i, n){
		vector<pair<R, int>> q;
		P st = s[i][1] - f[i];
		REP(j, p.size()) if(f[i].inside(p[j]) && !sig(norm(f[i]-p[j]) - f[i].r*f[i].r)){
			R ar = sig(norm(p[j]-s[i][1])) ? arg(((p[j]-f[i])/st) * P(-1, 0)) : f[i].cc == 1 ? -PI : PI;
			q.emplace_back(ar, j);
		}
		if(f[i].cc == 1) sort(ALL(q));
		else sort(RALL(q));
		REP(j, (int)q.size() - 1){
			e.emplace_back(mp(p[q[j].second], p[q[j+1].second]), f[i].r * abs(q[j].first - q[j+1].first));
			e.emplace_back(mp(p[q[j+1].second]+P(1000, 0), p[q[j].second]+P(1000, 0)), f[i].r * abs(q[j].first - q[j+1].first));
		}
	}
	
	n = p.size();
	vector<vector<pair<int, R>>> g(n);
	int start = lower_bound(ALL(p), s[0][0]) - p.begin();
	sort(ALL(e));UNIQUE(e);
	FOR(it, e){
		int u = lower_bound(ALL(p), it->first.first) - p.begin();
		int v = lower_bound(ALL(p), it->first.second) - p.begin();
		g[u].emplace_back(v, it->second);
	}
	
	printf("%.14f\n", dijkstra(g, start));
	return 0;
}