#include <cmath>
#include <climits>
#include <iostream>

using namespace std;

/*
	Geometry lib by Blaise1
*/

//magic numbers
using T = double;
const T EPS = 1e-12;
const T INF = 1e18;
//constants
const bool isTangentIntersection = false;

struct point {
	T x, y;

	point(T x, T y) : x(x), y(y) { }

	//Equal operator
	bool operator==(const point &o) const{
		return x == o.x ? (y == o.y ? true : false) : false;
	}

	//Unequal operator
	bool operator!=(const point &o) const{
		return !(*this == o);
	}

	//Sum of points
	point operator+(const point &o) const{
		return {x + o.x, y + o.y};
	}

	//Unary negation
	point operator-() const{
		return {-x, -y};
	}

	//Difference of points
	point operator-(const point &o) const{
		return *this + (-o);
	}

	//Scalar product
	point operator*(const T &d) const{
		return {x * d, y * d};
	}

	//Vectorial product (pointwise)
	point operator*(const point &o) const{
		return {x * o.x, y * o.y};
	}

	//Dot product
	T operator%(const point &o) const{
		return (*this * o).magnitude();
	}

	//Cross product
	T operator^(const point &o) const{
		return x * o.y - y * o.x;
	}

	//Distance between points
	T distance(const point &o) const{
		return hypot(fabs(x - o.x), fabs(y - o.y));
	}

	//Normalize
	point normalized() const{
		point tmp = {x, y};
		tmp.normalize();
		return tmp;
	}

	//Normalize
	void normalize(){
		T hy = hypot(x, y);
		x /= hy;
		y /= hy;
	}

	T magnitude() const{
		return x + y;
	}

	point rotated_rad(T rad) const{
		point tmp = {x, y};
		tmp.rotate_rad(rad);
		return tmp;
	}

	//O(log n)
	void rotate_rad(T rad){
		if(rad == M_PI/2){
			swap(x,y);
			x = -x;
		}else if(rad == -M_PI/2){
			swap(x,y);
			y = -y;
		} else if(rad == M_PI || rad == -M_PI){
			x = -x;
			y = -y;
		} else {
			T newx = x * cos(rad) - y * sin(rad);
			T newy = x * sin(rad) + y * cos(rad);
			x = newx;
			y = newy;
		}
	}

	T angle(const point& other) const{
		point self = this->normalized();
		point oth = other.normalized();
		if(self == oth)
			return 0;
		point origin = {0,0};

		T cos_alpha = self % oth;
		return fabs(acos(cos_alpha));
	}
};

struct line{
	//DO NOT MODIFY FOR ANY REASONS!!!
	//Create copies instead
	point dir;
	point perp;
	T a,b,c;

	line(T a, T b, T c) : perp(a,b), dir(0,0) {
		assert(!(a == 0 && b == 0));
		perp.normalize();
		dir = perp.rotated_rad(-M_PI/2);
		this->c = c / hypot(a,b);
		this->a = perp.x;
		this->b = perp.y;
	}

	line(point p1, point p2) : perp(0,0), dir(p2-p1) {
		assert(p1 != p2);
		dir.normalize();
		perp = dir.rotated_rad(M_PI/2);
		a = perp.x;
		b = perp.y;
		c = -(perp % p1);
	}

	T q() const{
		return -c / b;
	}

	T m() const{
		return -a / b;
	}

	bool inLine(const point &p) const{
		return fabs(dir.x * p.x + dir.y * p.y + c) <= EPS;
	}

	line operator-() const{
		line inv(-a,-b,-c);
		return inv;
	}

	bool operator==(const line &o) const{
		if(fabs(a) - fabs(o.a) > EPS)
			return false;
		line tmp(o);
		if(a != o.a)
			tmp = -tmp;

		if(fabs(a - tmp.a) <= EPS && fabs(b - tmp.b) <= EPS && fabs(c - tmp.c) <= EPS)
			return true;
		return false;
	}

	T signed_distance(const point &p) const{
		return perp % p + c;
	}

	point project(const point &p) const{
		T dist = signed_distance(p);
		return p - (perp * dist);
	}

	line parallel(const point &p) const{
		T dist = signed_distance(p);
		line res = *this;
		res.c -= dist;
		return res;
	}

	point intersect(const line &s) const{
		line l = *this;
		T d1 = l.a * s.b - s.a * l.b;
		//Check parallelism
		if(fabs(d1) <= EPS)
			return {-INF, -INF};
		T d2 = -d1;
		return { (s.c * l.b - l.c * s.b) / d1, (s.c * l.a - l.c * s.a) / d2 };
	}
};

struct segment{
	point start, end;

	segment(point p1, point p2) : start(p1), end(p2) { }

	bool lies(const point &a) const{
		point b = start;
		point c = end;
		line l(b,c);
		T dist = l.signed_distance(a);
		if(!(fabs(dist) <= EPS))
			return false;

		point ba = a-b;
		point bc = c-b;
		point ca = a-c;
		point cb = b-c;

		if(ba % bc < 0)
			return false;
		if(ca % cb < 0)
			return false;
		return true;
	}

	point intersect(const segment &s2) const{
		segment s1 = *this;
		line l1(s1.start, s1.end);
		line l2(s2.start, s2.end);

		point inter = l1.intersect(l2);
		point inf(-INF, -INF);
		//parallel
		if(inter == inf){
			//check endpoints
			if(l1 == l2){
				bool ok1 = s1.lies(s2.start);
				bool ok2 = s1.lies(s2.end);
				bool ok3 = s2.lies(s1.start);
				bool ok4 = s2.lies(s1.end);

				if(ok1)
					return s2.start;
				if(ok2)
					return s2.end;
				if(ok3)
					return s1.start;
				if(ok4)
					return s1.end;

				return inf;
			}
			return inf;
		}

		//check if s1 and s2 have inter
		if(s1.lies(inter) && s2.lies(inter))
			return inter;
		return inf;
	}

	T distance(const point &p) const{
		line l(start, end);
		point projection = l.project(p);
		if(lies(projection))
			return fabs(l.signed_distance(p));
		return min(start.distance(p), end.distance(p));
	}
};

struct half_plain{
	line l;

	half_plain(line l) : l(l) { }

	bool inPlain(const point &p) const{
		return l.dir.x * p.x + l.dir.y * p.y + l.c >= 0;
	}
};

struct circle{
	point centre;
	T radius;

	circle(point centre, T radius) : centre(centre), radius(radius) {}

	//point must be outside circle
	segment tangent_points(const point &p) const{
		//I dont p.distance(centre) cause of precision
		T pc_squared = fabs(p.x - centre.x)*fabs(p.x - centre.x) + fabs(p.y - centre.y)*fabs(p.y - centre.y);
		T ca_squared = radius*radius;
		T pa_squared = pc_squared - ca_squared;
		T pc = p.distance(centre);

		T dc = (pa_squared - ca_squared - pc_squared) / (-2 * pc);
		T pd = pc - dc;

		point pc_vec = centre - p;
		pc_vec.normalize();
		pc_vec = pc_vec * pd;
		point d = pc_vec + p;
		point da_vec = d.rotated_rad(M_PI/2);
		point db_vec = d.rotated_rad(-M_PI/2);
		da_vec.normalize();
		db_vec.normalize();

		T da = sqrt(pa_squared - pd*pd);
		da_vec = da_vec * da;
		point a = da_vec + d;
		db_vec = db_vec * da;
		point b = db_vec + d;

		return {a,b};
	}

	bool is_segment_intersecting(const segment &s) const{
		T dd = s.distance(centre);
		if(fabs(dd - radius) < EPS)
			return isTangentIntersection;	//tangent intersection
		if(dd > radius)
			return false;
		return true;
	}

	//a and b are in circonference
	T arc(const point &a, const point &b){
		point ca_vec = a - centre;
		point cb_vec = b - centre;
		T angle = ca_vec.angle(cb_vec);
		return radius * angle;
	}
};

int main(){k

	return 0;
}