#ifndef __GEOMETRIC_2D_H__
#define __GEOMETRIC_2D_H__

/* updated: 2020-07-25 */

#include <cstdint>
#include <utility>
#include <iostream>
#include <string>
#include <vector>

namespace Geometric2DInt {
	using Int = int64_t;
	using Radian = double;
	using Degree = double;

	const double PI = 3.14159265358979323;

	enum class CCWEnum : int {
		BackwardOnLine = -2,	// p-a--b
		Clockwise,
		Internal,
		Counterclockwise,
		ForwardOnLine,			//   a--b-p
	};

	struct PolarCoorinates {
		double norm;
		Radian arg;

		PolarCoorinates();
		PolarCoorinates(double norm, Radian arg);
		PolarCoorinates(const PolarCoorinates&) = default;
		PolarCoorinates& operator=(const PolarCoorinates&) = default;
	};

	int64_t GCD(int64_t a, int64_t b);

	Degree ragToDeg(Radian rad);
	Radian degToRad(Degree deg);

	template <class T>
	int sign(T value);

	template<class T>
	inline int sign(T value) {
		if (value > 0) return 1;
		if (value < 0) return -1;
		return 0;
	}

	struct Vector {
		Int x;
		Int y;

		Vector();
		Vector(Int x, Int y);
		explicit Vector(const std::pair<Int, Int>& pair);
		Vector(const Vector&) = default;

		Vector& operator=(const Vector&) = default;

		const Vector& operator+() const;
		Vector operator-() const;
		Vector& operator+=(const Vector& right);
		Vector& operator-=(const Vector& right);
		Vector& operator*=(Int scalar);

		bool isZero() const;
		Int norm2() const;
		double norm() const;
		Radian arg() const;
		PolarCoorinates toPolar() const;

		bool argIsLessThenPi() const;

		/* for map */
		static int compare(const Vector& left, const Vector& right);
		static int compareByArg(const Vector& left, const Vector& right);
	};

	bool operator==(const Vector& left, const Vector& right);
	bool operator!=(const Vector& left, const Vector& right);
	bool operator<(const Vector& left, const Vector& right);
	bool operator<=(const Vector& left, const Vector& right);
	bool operator>(const Vector& left, const Vector& right);
	bool operator>=(const Vector& left, const Vector& right);

	Vector operator+(const Vector& left, const Vector& right);
	Vector operator-(const Vector& left, const Vector& right);
	Vector operator*(const Vector& vec, Int scalar);
	Vector operator*(Int scalar, const Vector& vec);

	std::istream& operator>>(std::istream& ist, Vector& vec);
	std::ostream& operator<<(std::ostream& ost, const Vector& vec);

	Int dot(const Vector& a, const Vector& b);
	Int cross(const Vector& a, const Vector& b);
	bool isOrthogonal(const Vector& a, const Vector& b);
	bool isParallel(const Vector& a, const Vector& b);
	Radian angle(const Vector& from, const Vector& to);
	Radian angle(const Vector& from, const Vector& center, const Vector& to);
	Radian angle2Pi(const Vector& from, const Vector& to);
	Radian angle2Pi(const Vector& from, const Vector& center, const Vector& to);
	CCWEnum ccw(const Vector& a, const Vector& b, const Vector& p);
	
	/* 直線 ax + by = c を normal = (a, b) と c で表す */
	/* GCD(a, b) > 0 を認めるか？ */
	struct Segment;
	struct Line {
		Vector normal;
		Int constant;

		Line();
		Line(Int a, Int b, Int c);
		Line(const Vector& normal, Int constant);
		Line(const Vector& p, const Vector& q);
		explicit Line(const Segment& s);
		Line(const Line&) = default;
		Line& operator=(const Line&) = default;

	private:
		void reduce();

	public:
		bool contains(const Vector& p) const;

		/* for map */
		static int compare(const Line& left, const Line& right);
	};

	bool operator==(const Line& left, const Line& right);
	bool operator!=(const Line& left, const Line& right);
	bool operator<(const Line& left, const Line& right);
	bool operator<=(const Line& left, const Line& right);
	bool operator>(const Line& left, const Line& right);
	bool operator>=(const Line& left, const Line& right);

	double distance(const Line& l, const Vector& p);
	//Line Reflect(const Line& object, const Line& axis);
	bool isOrthogonal(const Line& a, const Line& b);
	bool isParallel(const Line& a, const Line& b);

	/* 無向 */
	struct Segment {
		Vector a;
		Vector b;

		Segment();
		Segment(const Vector& a_arg, const Vector& b_arg);
		explicit Segment(const std::pair<Vector, Vector>& pair);
		Segment(const Segment&) = default;
		Segment& operator=(const Segment&) = default;

		/* for map */
		static int compare(const Segment& left, const Segment& right);

		// bool contains(const Vector& p) const;
	};

	bool operator==(const Segment& left, const Segment& right);
	bool operator!=(const Segment& left, const Segment& right);
	bool operator<(const Segment& left, const Segment& right);
	bool operator<=(const Segment& left, const Segment& right);
	bool operator>(const Segment& left, const Segment& right);
	bool operator>=(const Segment& left, const Segment& right);

	double distance(const Segment& s, const Vector& p);
	bool hasIntersection(const Segment& s, const Segment& t);
	bool hasIntersection(const Segment& s, const Line& l);
	bool hasIntersection(const Line& l, const Segment& s);

	/* 基本的に反時計回りとする */
	struct Polygon {
		std::vector<Vector> points;

		Polygon() = default;
		Polygon(const std::vector<Vector>& points);
		Polygon(std::initializer_list<Vector> points);
		Polygon(const Polygon&) = default;
		Polygon& operator=(const Polygon&) = default;

		Vector& operator[](int index);
		const Vector& operator[](int index) const;
		
		static int modPositive(int val, int mod);

		void add(const Vector& p);
		void reverse();

		int size() const;
		Int areaTwice(bool oriented = false) const;
		bool isConvex(bool oriented = false) const;
	};

	/* 反時計回りに限定するか？ 面積は正負を考えるか？ */
	struct Triangle {
		Vector a;
		Vector b;
		Vector c;

		Triangle();
		Triangle(const Vector& a, const Vector& b, const Vector& c);
		Triangle(const Triangle&) = default;
		Triangle& operator=(const Triangle&) = default;

	private:
		void reduce();

	public:
		Int areaTwice() const;
	};

	Polygon convexHull(const std::vector<Vector>& points_arg, bool is_strict = true);
	int farthestPointConvex(const Polygon& polygon, const Vector& dir);
}

#endif

#ifdef ONLY_MY_ENVIR
#include "Geometric2D.h"
#endif

#include <cmath>
#include <cassert>
#include <algorithm>

namespace Geometric2DInt {
	PolarCoorinates::PolarCoorinates()
		: PolarCoorinates(0, 0) {
	}

	PolarCoorinates::PolarCoorinates(double norm, Radian arg)
		: norm(norm), arg(arg) {
	}

	int64_t GCD(int64_t a, int64_t b) {
		if (b == 0) return a;
		return GCD(b, a % b);
	}

	Degree ragToDeg(Radian rad) {
		return rad * 180 / PI;
	}

	Radian degToRad(Degree deg) {
		return deg * PI / 180;
	}

	/*---------------------------------*/
	/*-----------   Vector   ----------*/
	/*---------------------------------*/

	Vector::Vector()
		: Vector(0, 0) {
	}

	Vector::Vector(Int x, Int y)
		: x(x), y(y) {
	}

	Vector::Vector(const std::pair<Int, Int>& pair)
		: Vector(pair.first, pair.second) {
	}

	const Vector& Vector::operator+() const {
		return *this;
	}

	Vector Vector::operator-() const {
		return Vector(-x, -y);
	}

	Vector& Vector::operator+=(const Vector& right) {
		x += right.x;
		y += right.y;
		return *this;
	}

	Vector& Vector::operator-=(const Vector& right) {
		x -= right.x;
		y -= right.y;
		return *this;
	}

	Vector& Vector::operator*=(Int scalar) {
		x *= scalar;
		y *= scalar;
		return *this;
	}

	bool Vector::isZero() const {
		return x == 0 && y == 0;
	}

	Int Vector::norm2() const {
		return x * x + y * y;
	}

	double Vector::norm() const {
		return std::sqrt(norm2());
	}

	/* [0, 2PI] */
	Radian Vector::arg() const {
		Radian arg = std::atan2(y, x);
		if (arg < 0) {
			arg += 2 * PI;
		}
		return arg;
	}

	PolarCoorinates Vector::toPolar() const {
		return PolarCoorinates(norm(), arg());
	}

	/* 角度が [0, pi) に含まれるかどうか */
	bool Vector::argIsLessThenPi() const {
		return y > 0 || (x >= 0 && y >= 0);
	}

	int Vector::compare(const Vector& left, const Vector& right) {
		if (left.x > right.x) return 1;
		if (left.x < right.x) return -1;
		if (left.y > right.y) return 1;
		if (left.y < right.y) return -1;
		return 0;
	}

	/* 偏角で並べる, 偏角が等しいものは同じとみなす(そのため set などには使えない) */
	int Vector::compareByArg(const Vector& left, const Vector& right) {
		/* ゼロベクトルは最も小さいとする */
		if (left.isZero()) return right.isZero() ? 0 : -1;
		if (right.isZero()) return 1;

		/* どちらか1つの偏角が PI 以上の場合、そちらが大きい */
		bool left_less = left.argIsLessThenPi();
		bool right_less = right.argIsLessThenPi();
		if (left_less && !right_less) return -1;
		if (!left_less && right_less) return 1;

		/* 両方とも PI より小さいか、PI 以上の場合は外積で比較 */
		return -sign(cross(left, right));
	}

	bool operator==(const Vector& left, const Vector& right) {
		return Vector::compare(left, right) == 0;
	}

	bool operator!=(const Vector& left, const Vector& right) {
		return Vector::compare(left, right) != 0;
	}

	bool operator<(const Vector& left, const Vector& right) {
		return Vector::compare(left, right) < 0;
	}

	bool operator<=(const Vector& left, const Vector& right) {
		return Vector::compare(left, right) <= 0;
	}

	bool operator>(const Vector& left, const Vector& right) {
		return Vector::compare(left, right) > 0;
	}

	bool operator>=(const Vector& left, const Vector& right) {
		return Vector::compare(left, right) >= 0;
	}

	Vector operator+(const Vector& left, const Vector& right) {
		Vector ret(left);
		ret += right;
		return ret;
	}

	Vector operator-(const Vector& left, const Vector& right) {
		Vector ret(left);
		ret -= right;
		return ret;
	}

	Vector operator*(const Vector& vec, Int scalar) {
		Vector ret(vec);
		ret *= scalar;
		return ret;
	}

	Vector operator*(Int scalar, const Vector& vec) {
		Vector ret(vec);
		ret *= scalar;
		return ret;
	}

	std::istream& operator>>(std::istream& ist, Vector& vec) {
		ist >> vec.x >> vec.y;
		return ist;
	}

	std::ostream& operator<<(std::ostream& ost, const Vector& vec) {
		ost << vec.x << ' ' << vec.y;
		return ost;
	}

	Int dot(const Vector& a, const Vector& b) {
		return a.x * b.x + a.y * b.y;
	}

	Int cross(const Vector& a, const Vector& b) {
		return a.x * b.y - a.y * b.x;
	}

	bool isOrthogonal(const Vector& a, const Vector& b) {
		return dot(a, b) == 0;
	}

	/* ゼロベクトルとは「平行」と判定されるので注意(同値関係にならない) */
	bool isParallel(const Vector& a, const Vector& b) {
		return cross(a, b) == 0;
	}

	/* [0, PI) */
	Radian angle(const Vector& from, const Vector& to) {
		double cos_th = dot(from, to) / (from.norm() * to.norm());
		if (cos_th > 1) cos_th = 1;
		if (cos_th < -1) cos_th = -1;
		return std::acos(cos_th);
	}

	Radian angle(const Vector& from, const Vector& center, const Vector& to) {
		return angle(from - center, to - center);
	}

	/* [0, 2 * PI) */
	Radian angle2Pi(const Vector& from, const Vector& to) {
		return angle2Pi(from, Vector(), to);
	}

	Radian angle2Pi(const Vector& from, const Vector& center, const Vector& to) {
		Radian angle = (to - center).arg() - (from - center).arg();
		if (angle < 0) angle += 2 * PI;
		return angle;
	}

	CCWEnum ccw(const Vector& a, const Vector& b, const Vector& p) {
		Vector ab = b - a;
		Vector ap = p - a;
		Int crs = cross(ab, ap);
		if (crs > 0) return CCWEnum::Counterclockwise;
		if (crs < 0) return CCWEnum::Clockwise;
		if (dot(ab, ap) < 0) return CCWEnum::BackwardOnLine;
		if (ab.norm2() < ap.norm2()) return CCWEnum::ForwardOnLine;
		return CCWEnum::Internal;
	}

	/*---------------------------------*/
	/*------------   Line   -----------*/
	/*---------------------------------*/

	Line::Line()
		: Line(Vector(1, 0), 0) {
	}

	/* 直線 ax + by + c = 0 */
	Line::Line(Int a, Int b, Int c)
		: Line(Vector(a, b), -c) {
	}

	Line::Line(const Vector& normal, Int constant)
		: normal(normal), constant(constant) {
		reduce();
	}

	/* (x_1, y_1), (x_2, y_2) を通る直線 → 直線 -(y_2 - y_1)x + (x_2 - x_1)y + (x_1 y_2 - x_2 y_1) = 0 */
	Line::Line(const Vector& p, const Vector& q)
		: Line(p.y - q.y, q.x - p.x, cross(p, q)) {
	}

	Line::Line(const Segment& s)
		: Line(s.a, s.b) {
	}

	/* 表現を一意にする */
	void Line::reduce() {
		assert(!normal.isZero());

		/* normal と c の値は既約とする */
		std::vector<Int> list{ normal.x, normal.y, constant };
		Int gcd = 0;

		for (Int element : list) {
			gcd = GCD(gcd, std::abs(element));
		}

		/* 0 <= normal.arg < PI とする */
		if (!normal.argIsLessThenPi()) {
			gcd = -gcd;
		}

		normal.x /= gcd;
		normal.y /= gcd;
		constant /= gcd;
	}

	bool Line::contains(const Vector& p) const {
		return dot(normal, p) == constant;
	}

	int Line::compare(const Line& left, const Line& right) {
		if (left.normal < right.normal) return -1;
		if (left.normal > right.normal) return 1;
		if (left.constant < right.constant) return -1;
		if (left.constant > right.constant) return 1;
		return 0;
	}

	bool operator==(const Line& left, const Line& right) {
		return Line::compare(left, right) == 0;
	}

	bool operator!=(const Line& left, const Line& right) {
		return Line::compare(left, right) != 0;
	}

	bool operator<(const Line& left, const Line& right) {
		return Line::compare(left, right) < 0;
	}

	bool operator<=(const Line& left, const Line& right) {
		return Line::compare(left, right) <= 0;
	}

	bool operator>(const Line& left, const Line& right) {
		return Line::compare(left, right) > 0;
	}

	bool operator>=(const Line& left, const Line& right) {
		return Line::compare(left, right) >= 0;
	}

	double distance(const Line& l, const Vector& p) {
		Vector n = l.normal;
		return abs(dot(n, p) - l.constant) / n.norm();
	}

	bool isOrthogonal(const Line& a, const Line& b) {
		return isOrthogonal(a.normal, b.normal);
	}

	bool isParallel(const Line& a, const Line& b) {
		return isParallel(a.normal, b.normal);
	}

	/*---------------------------------*/
	/*----------   Segment   ----------*/
	/*---------------------------------*/

	Segment::Segment()
		: Segment(Vector(), Vector()) {
	}

	Segment::Segment(const Vector& a_arg, const Vector& b_arg)
		: a(a_arg), b(b_arg) {

		assert(a != b);
		if (a > b) {
			std::swap(a, b);
		}
	}

	Segment::Segment(const std::pair<Vector, Vector>& pair)
		: Segment(pair.first, pair.second) {
	}

	int Segment::compare(const Segment& left, const Segment& right) {
		if (left.a < right.a) return -1;
		if (left.a > right.a) return 1;
		if (left.b < right.b) return -1;
		if (left.b > right.b) return 1;
		return 0;
	}
	
	bool operator==(const Segment& left, const Segment& right) {
		return Segment::compare(left, right) == 0;
	}

	bool operator!=(const Segment& left, const Segment& right) {
		return Segment::compare(left, right) != 0;
	}

	bool operator<(const Segment& left, const Segment& right) {
		return Segment::compare(left, right) < 0;
	}

	bool operator<=(const Segment& left, const Segment& right) {
		return Segment::compare(left, right) <= 0;
	}

	bool operator>(const Segment& left, const Segment& right) {
		return Segment::compare(left, right) > 0;
	}

	bool operator>=(const Segment& left, const Segment& right) {
		return Segment::compare(left, right) >= 0;
	}

	double distance(const Segment& s, const Vector& p) {
		/* 点 a が最も近い */
		Vector ab = s.b - s.a;
		Vector ap = p - s.a;
		if (dot(ab, ap) <= 0) return ap.norm();

		/* 点 b が最も近い */
		Vector ba = -ab;
		Vector bp = p - s.b;
		if (dot(ba, bp) <= 0) return bp.norm();

		/* それ以外 → 点と直線の距離 */
		return distance(Line(s), p);
	}

	bool hasIntersection(const Segment& s, const Segment& t) {
		return (int)ccw(s.a, s.b, t.a) * (int)ccw(s.a, s.b, t.b) <= 0
			&& (int)ccw(t.a, t.b, s.a) * (int)ccw(t.a, t.b, s.b) <= 0;
	}

	bool hasIntersection(const Segment& s, const Line& l) {
		return sign(dot(s.a, l.normal)) * sign(dot(s.b, l.normal)) <= 0;
	}

	bool hasIntersection(const Line& l, const Segment& s) {
		return hasIntersection(s, l);
	}

	/*---------------------------------*/
	/*-----------   Polygon   ---------*/
	/*---------------------------------*/

	Polygon::Polygon(const std::vector<Vector>& points)
		: points(points) {
	}

	Polygon::Polygon(std::initializer_list<Vector> points)
		: points(points) {
	}

	Vector& Polygon::operator[](int index) {
		const int N = size();
		assert(N > 0);
		return points[modPositive(index, N)];
	}

	const Vector& Polygon::operator[](int index) const {
		const int N = size();
		assert(N > 0);
		return points[modPositive(index, N)];
	}

	/* 0 <= x && x < mod の範囲に入るような剰余計算 */
	int Polygon::modPositive(int val, int mod) {
		assert(mod > 0);
		if (val < 0) return (mod - 1) - (~val) % mod;
		return val % mod;
	}

	void Polygon::add(const Vector& point) {
		points.push_back(point);
	}

	void Polygon::reverse() {
		std::reverse(points.begin(), points.end());
	}

	int Polygon::size() const {
		return points.size();
	}

	Int Polygon::areaTwice(bool oriented) const {
		const int N = size();
		if (N <= 2) return 0;

		Int sum = 0;
		for (int i = 0; i < N; ++i) {
			Vector a = points[i];
			Vector b = points[i == N - 1 ? 0 : i + 1];
			sum += cross(a, b);
		}
		return oriented ? sum : std::abs(sum);
	}

	/* 同一直線上にある場合を考慮していない && 自己交差も考えていない */
	bool Polygon::isConvex(bool oriented) const {
		const int N = size();
		if (N <= 2) return true;

		CCWEnum first_ccw = ccw(points[0], points[1], points[2]);
		if (oriented) {
			if (first_ccw != CCWEnum::Counterclockwise) return false;
		}

		for (int i = 1; i < N; ++i) {
			const Vector& a = points[i];
			const Vector& b = points[(i + 1) % N];
			const Vector& c = points[(i + 2) % N];
			if (first_ccw != ccw(a, b, c)) return false;
		}
		return true;
	}

	/*---------------------------------*/
	/*----------   Triangle   ---------*/
	/*---------------------------------*/

	Triangle::Triangle()
		: Triangle(Vector(), Vector(), Vector()) {
	}

	Triangle::Triangle(const Vector& a, const Vector& b, const Vector& c)
		: a(a), b(b), c(c) {
		reduce();
	}

	void Triangle::reduce() {
		/* sort */
		if (a > b) std::swap(a, b);
		if (b > c) std::swap(b, c);
		if (a > b) std::swap(a, b);
	}

	Int Triangle::areaTwice() const {
		Int crs = cross(b - a, c - a);
		return std::abs(crs);
	}

	/*---------------------------------*/
	/*---------   グローバル   --------*/
	/*---------------------------------*/

	/* 点群の凸包を構成 O(n log n) */
	/* 一直線上に並ぶ点を保持するなら is_strict == false とする (同一点は保持しないので注意) */
	// verified CGL_4_A (is_strict == false)
	Polygon convexHull(const std::vector<Vector>& points_arg, bool is_strict) {
		/* 凸包上の位置関係として望ましいかどうか */
		auto isInPlace = [is_strict](const Vector& a, const Vector& b, const Vector& c) -> bool {
			CCWEnum res = ccw(a, b, c);
			if (is_strict) {
				return res == CCWEnum::Counterclockwise;
			} else {
				return res == CCWEnum::Counterclockwise || res == CCWEnum::ForwardOnLine;
			}
		};

		/* 凸包の半分を構成 */
		auto constructHalf = [isInPlace](const std::vector<Vector>& points) -> std::vector<Vector> {
			std::vector<Vector> ret;
			for (const Vector& point : points) {
				/* 望ましい位置関係になるまで点を削除 */
				while (true) {
					int n = ret.size();
					if (n < 2) break;
					if (isInPlace(ret[n - 2], ret[n - 1], point)) break;
					ret.pop_back();
				}
				ret.push_back(point);
			}
			ret.pop_back();		// 上下を合わせた際に重複しないよう終点を削除しておく
			return ret;
		};

		std::vector<Vector> points(points_arg);
		sort(points.begin(), points.end());		// x座標でソート
		
		Polygon ret;

		/* 下半分を構成 */
		for (const Vector& vertex : constructHalf(points)) {
			ret.add(vertex);
		}

		/* 点の並びを反転させてもう一度実行 */
		reverse(points.begin(), points.end());

		/* 下半分を構成 */
		for (const Vector& vertex : constructHalf(points)) {
			ret.add(vertex);
		}

		return ret;
	}

	/* 凸多角形に対して、ベクトル dir 方向に最も遠い点 (dir との内積が最大の点) の添字を返す O(log n) */
	/* polygon は狭義凸である必要がある(一直線上に並ぶ三点があってはならない) */
	int farthestPointConvex(const Polygon& polygon, const Vector& dir) {
		/* 目的関数値 */
		auto f = [&polygon, &dir](int i) -> Int {
			return dot(polygon[i], dir);
		};

		assert(polygon.size() > 0);
		if (polygon.size() == 1) return 0;

		//if (f(0) == f(1)) {
		//	/* f(0) == f(1) のとき、f(0) は最大値か最小値である */
		//	/* 最大値であるケースを先に判定しておく */
		//	if (f(0) > f(-1)) return 0;
		//}

		if (f(1) >= f(0)) {
			/* i == 0 における傾きが正のとき */
			/* [値 >= f(0) かつ 傾き >= 0] の領域 (lo) とそれ以外 (hi) で二分探索 */
			int lo = 0;
			int hi = polygon.size();

			while (hi - lo > 1) {
				int mid = (lo + hi) / 2;
				if (f(mid) >= f(0) && f(mid + 1) >= f(mid)) {
					lo = mid;
				} else {
					hi = mid;
				}
			}
			return hi;
		} else {
			/* i == 0 における傾きが負のとき */
			/* [値 >= f(0) かつ 傾き < 0] の領域 (hi) とそれ以外 (lo) で二分探索 */
			int lo = 0;
			int hi = polygon.size();

			while (hi - lo > 1) {
				int mid = (lo + hi) / 2;
				if (f(mid) >= f(0) && f(mid + 1) < f(mid)) {
					hi = mid;
				} else {
					lo = mid;
				}
			}
			return hi;
		}
	}
}
#define _CRT_SECURE_NO_WARNINGS
#define _SCL_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <limits>
#include <numeric>
#include <valarray>
#include <fstream>
#include <array>
#include <random>
#include <unordered_set>
#include <unordered_map>

using namespace std;
using uint = uint32_t;
using LL = int64_t;
using ULL = uint64_t;
using PP = pair<LL, LL>;
template <typename T> using PriorityQ = priority_queue<T, vector<T>, greater<T> >;
#define REP(i, a, n) for(LL i = (a), i##_max_ = (n); i < i##_max_; ++i)
#define REM(i, a, n) for(LL i = (LL)(n) - 1, i##_min_ = (a); i >= i##_min_; --i)
#define FLOAT fixed << setprecision(16)
#define SPEEDUP { cin.tie(NULL); ios::sync_with_stdio(false); }
const int INF = 0x3FFFFFFF;
const LL INFLL = 0x3FFFFFFF3FFFFFFF;
const double INFD = 1.0e+308;
const double EPS = 1.0e-9;

void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
template <class T, class U> istream& operator>>(istream& ist, pair<T, U>& right) { return ist >> right.first >> right.second; }
template <class T, class U> ostream& operator<<(ostream& ost, const pair<T, U>& right) { return ost << right.first << ' ' << right.second; }
template <class T, class TCompatible, size_t N> void Fill(T(&dest)[N], const TCompatible& val) { fill(dest, dest + N, val); }
template <class T, class TCompatible, size_t M, size_t N> void Fill(T(&dest)[M][N], const TCompatible& val) { for (int i = 0; i < M; ++i) Fill(dest[i], val); }
template <class T> T Next() { T buf; cin >> buf; return buf; }
istream& Ignore(istream& ist) { string s; ist >> s; return ist; }
bool Inside(int i, int j, int h, int w) { return i >= 0 && i < h && j >= 0 && j < w; }

#ifdef ONLY_MY_ENVIR
#include "Accumulator.h"
#include "Algebraic.h"
#include "BinaryMatrix.h"
#include "BinaryTree.h"
#include "Bipartite.h"
#include "BIT.h"
#include "Compressor.h"
#include "Decompositions.h"
#include "DiscreteLog.h"
#include "DynamicMod.h"
#include "Exponential.h"
#include "Factorization.h"
#include "FFT.h"
#include "FlowSolver.h"
#include "Geometric2D.h"
#include "Geometric2DFloat.h"
#include "Geometric3D.h"
#include "Geometric3DFloat.h"
#include "Graph.h"
#include "GraphUtil.h"
#include "Interpolation.h"
#include "IntMod.h"
#include "KDTree.h"
#include "LazySegmentTree.h"
#include "LIS.h"
#include "Math.h"
#include "MathUtil.h"
#include "Matrix.h"
#include "MinCostFlowSolver.h"
#include "MinMax.h"
#include "Numbers.h"
#include "Optimize.h"
#include "Permutation.h"
#include "Polynomial.h"
#include "Position.h"
#include "Random.h"
#include "Range.h"
#include "Rational.h"
#include "RuntimeMod.h"
#include "SegmentTree.h"
#include "SegmentTree2D.h"
#include "Sets.h"
#include "Shortest.h"
#include "SlidingWindow.h"
#include "SpanningTree.h"
#include "StringSearching.h"
#include "SuffixArray.h"
#include "SwitchList.h"
#include "Timer.h"
#include "Tree.h"
#include "TreeUtil.h"
#include "UnionFind.h"
#include "Util.h"
#include "VectorUtil.h"
#endif

#ifdef __GNUC__
typedef __int128 LLL;
istream& operator>>(istream& ist, __int128& val) { LL tmp; ist >> tmp; val = tmp; return ist; }
ostream& operator<<(ostream& ost, __int128 val) { LL tmp = val; ost << tmp; return ost; }
#endif

int main() {
	using namespace Geometric2DInt;

	int N;
	cin >> N;
	vector<Vector> vs;
	REP(i, 0, N) {
		Vector v;
		cin >> v;
		vs.push_back(v);
	}

	auto poly = convexHull(vs);

	vector<double> ans;
	REP(k, 0, poly.size()) {
		double rad = angle(poly[k - 1], poly[k], poly[k + 1]);
		ans.push_back((PI - rad) / (2 * PI));
	}

	REP(i, 0, N) {
		bool ok = false;
		REP(k, 0, poly.size()) {
			if (vs[i] == poly[k]) {
				cout << FLOAT << ans[k] << endl;
				ok = true;
				break;
			}
		}
		if (!ok) {
			cout << FLOAT << 0.0 << endl;
		}
	}

	return 0;
}





Measured memory_bytes: 4152