Language: C++

#include <cstdint>
#ifndef __MATH_H__
#define __MATH_H__

#include <vector>

uint64_t GCD(uint64_t a, uint64_t b);
uint64_t LCM(uint64_t a, uint64_t b);

uint64_t GCD(const std::vector<uint64_t>& values);
uint64_t LCM(const std::vector<uint64_t>& values);

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;
}


/* Representative * Relation = Representative みたいなノリ */
/* ゆくゆくは Relation * Relation = Relation に */
/* 範囲外アクセスなど注意; validation check必要 */
template <class T>
class RecurrenceRelation;
template <class T>
class RecurrenceRelationRepresentative {
	std::vector<T> coeffs_m;

	int Order() const;
public:
	//RecurrenceRelationRepresentative();
	RecurrenceRelationRepresentative(int order);
	RecurrenceRelationRepresentative(const std::vector<T> coeffs);
	const T& operator[](int index) const;
	T& operator[](int index);

	RecurrenceRelationRepresentative Successor(const RecurrenceRelation<T>& relation) const;
	T Real_value(const std::vector<T>& initial_vals);
};

template<class T>
inline int RecurrenceRelationRepresentative<T>::Order() const {
	return coeffs_m.size();
}

//template<class T>
//inline RecurrenceRelationRepresentative<T>::RecurrenceRelationRepresentative() {}

/* デフォルトコンストラクタは第0項目を表現 */
template<class T>
inline RecurrenceRelationRepresentative<T>::RecurrenceRelationRepresentative(int order) {
	coeffs_m.resize(order);
	coeffs_m[0] = 1;
}

template<class T>
inline RecurrenceRelationRepresentative<T>::RecurrenceRelationRepresentative(const std::vector<T> coeffs)
	: coeffs_m(coeffs){
}

template<class T>
inline const T& RecurrenceRelationRepresentative<T>::operator[](int index) const {
	return coeffs_m.at(index);
}

template<class T>
inline T& RecurrenceRelationRepresentative<T>::operator[](int index) {
	return coeffs_m.at(index);
}

template<class T>
inline RecurrenceRelationRepresentative<T> RecurrenceRelationRepresentative<T>::Successor(const RecurrenceRelation<T>& relation) const {
	std::vector<T> vec;
	vec.reserve(Order());
	vec.push_back(coeffs_m[Order() - 1]);
	for (int i = 1; i < Order(); ++i) {
		vec.push_back(coeffs_m[i - 1] + coeffs_m[Order() - 1] * relation[i]);
	}
	return RecurrenceRelationRepresentative(vec);
}

template<class T>
inline T RecurrenceRelationRepresentative<T>::Real_value(const std::vector<T>& initial_vals) {
	return inner_product(coeffs_m.begin(), coeffs_m.end(), initial_vals.begin(), T());
}


template <class T>
class RecurrenceRelation {
	typedef RecurrenceRelationRepresentative<T> Representative;

	/* 配列 v[k] で a[n + k] = v[0]a[n] + v[1]a[n + 1] + ... + v[k - 1]a[n + k - 1] の形の漸化式を表す */
	std::vector<T> relation_m;

	int Order() const;
	Representative Linear_expression(int index) const;
public:
	RecurrenceRelation(int size);
	RecurrenceRelation(const std::vector<T>& vec);
	T Real_value(int index, const std::vector<T>& initial_vals);

	const T& operator[](int index) const;
	T& operator[](int index);
};

template<class T>
int RecurrenceRelation<T>::Order() const {
	return relation_m.size();
}

template<class T>
typename RecurrenceRelation<T>::Representative RecurrenceRelation<T>::Linear_expression(int index) const {
	if (index == 0) return Representative(Order());

	std::vector<T> vec;
	std::vector<Representative> Sn;
	Sn.reserve(Order());

	int n = index / 2;
	Sn.push_back(Linear_expression(n));
	for (int k = 1; k < Order(); ++k) {
		Sn.push_back(Sn.back().Successor(*this));
	}
	for (int j = 0; j < Order(); ++j) {
		T sum = T();
		for (int p = 0; p < Order(); ++p) {
			sum += Sn[0][p] * Sn[p][j];
		}
		vec.push_back(sum);
	}
	
	Representative ret(vec);
	return index % 2 == 0 ? ret : ret.Successor(*this);
}

template<class T>
inline RecurrenceRelation<T>::RecurrenceRelation(int size)
	: relation_m(size, 1) {
}

template<class T>
RecurrenceRelation<T>::RecurrenceRelation(const std::vector<T>& vec)
	: relation_m(vec) {
}

template<class T>
T RecurrenceRelation<T>::Real_value(int index, const std::vector<T>& initial_vals) {
	Representative coeffs = Linear_expression(index);
	return coeffs.Real_value(initial_vals);
}

template<class T>
inline const T& RecurrenceRelation<T>::operator[](int index) const {
	return relation_m[index];
}

template<class T>
inline T& RecurrenceRelation<T>::operator[](int index) {
	return relation_m[index];
}


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

#include <numeric>

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

uint64_t LCM(uint64_t a, uint64_t b) {
	return a / GCD(a, b) * b;
}

uint64_t GCD(const std::vector<uint64_t>& values) {
	using FuncType = uint64_t (*)(uint64_t, uint64_t);
	return std::accumulate(values.begin(), values.end(), 0Ui64, (FuncType)GCD);
}

uint64_t LCM(const std::vector<uint64_t>& values) {
	using FuncType = uint64_t(*)(uint64_t, uint64_t);
	return std::accumulate(values.begin(), values.end(), 1Ui64, (FuncType)LCM);
}



#ifndef __GEOMETRY_H__
#define __GEOMETRY_H__

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

// 注意
#define Rational double
#define Vector2DDouble Vector2DInt
#define Vector2DRational Vector2DInt
#define LineSegmentDirected LineSegment



using Radian = double;
using Degree = double;

const double PI = 3.14159265358979323;

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

struct PolarCoorinates {
	double norm;
	Radian arg;

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

Degree Rad_to_deg(Radian rad);
Radian Deg_to_rad(Degree deg);
//Radian Regularize_rad(Radian rad);
//Degree Regularize_deg(Degree rad);


struct Vector2DInt {
	int x = 0;
	int y = 0;

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

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

	const Vector2DInt& operator+() const;
	Vector2DInt operator-() const;
	Vector2DInt& operator+=(const Vector2DInt& right);
	Vector2DInt& operator-=(const Vector2DInt& right);
	Vector2DInt& operator*=(int scalar);
	Vector2DInt& operator/=(int scalar);		// これどうしようか？

	bool Is_zero() const;
	long long Norm2() const;
	double Norm() const;
	Radian Arg() const;
	PolarCoorinates To_polar() const;

	bool Arg_is_less_than_pi() const;

	/* for map */
	static int Compare(const Vector2DInt& left, const Vector2DInt& right);
	static int CompareArg(const Vector2DInt& left, const Vector2DInt& right);
};

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

Vector2DInt operator+(const Vector2DInt& left, const Vector2DInt& right);
Vector2DInt operator-(const Vector2DInt& left, const Vector2DInt& right);
Vector2DInt operator*(const Vector2DInt& vec, int scalar);
Vector2DInt operator*(int scalar, const Vector2DInt& vec);
Vector2DRational operator/(const Vector2DInt& vec, int scalar);

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

long long Dot(const Vector2DInt& left, const Vector2DInt& right);
long long Cross(const Vector2DInt& left, const Vector2DInt& right);
bool Is_orthogonal(const Vector2DInt& a, const Vector2DInt& b);
bool Is_parallel(const Vector2DInt& a, const Vector2DInt& b);
Radian Angle(const Vector2DInt& from, const Vector2DInt& center, const Vector2DInt& to);
Vector2DDouble Internal(const Vector2DInt& a, const Vector2DInt& b, double ratio);
Vector2DRational Project(const Vector2DInt& object, const Vector2DInt& direction);
CCWEnum CCW(const Vector2DInt& a, const Vector2DInt& b, const Vector2DInt& p);


/* 無向 */
struct LineSegment {
	Vector2DInt start;
	Vector2DInt end;

	LineSegment();
	LineSegment(const Vector2DInt& point_a, const Vector2DInt& point_b);
	explicit LineSegment(const std::pair<Vector2DInt, Vector2DInt>& pair);
	LineSegment(const LineSegment&) = default;
	LineSegment& operator=(const LineSegment&) = default;

	/* for map */
	static int Compare(const LineSegment& left, const LineSegment& right);
};
double Distance_segment_vector(const LineSegment& segment, const Vector2DInt& vec);
Vector2DDouble Internal(const LineSegmentDirected& segment, double ratio);
bool Has_Intersection_point(const LineSegment& a, const LineSegment& b);

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

/* 直線 ax + by + c = 0 を normal = (a, b) と c で表す */
struct Line {
	Vector2DInt normal;
	int c;		// long long?

	Line();
	Line(int a, int b, int c);
	Line(const Vector2DInt& normal, int c);
	Line(const Vector2DInt& p, const Vector2DInt& q);
	explicit Line(const LineSegment& segment);
	Line(const Line&) = default;
	Line& operator=(const Line&) = default;
private:
	void Reduce();
public:
	bool Is_on(const Vector2DRational& point) const;
	Rational value_y_where_x_is(int x) const;
	Rational value_x_where_y_is(int y) const;

	LineSegment To_segment() 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_line_vector(const Line& line, const Vector2DInt& vec);
Vector2DRational Project(const Vector2DInt& object, const Line& direction);
Vector2DRational Reflect(const Vector2DInt& object, const Line& axis);
LineSegment Reflect(const LineSegment& object, const Line& axis);
Line Reflect(const Line& object, const Line& axis);
bool Has_Intersection_point(const LineSegment& segment, const Line& line);
bool Has_Intersection_point(const Line& line, const LineSegment& segment);
bool Is_orthogonal(const Line& a, const Line& b);
bool Is_parallel(const Line& a, const Line& b);

Vector2DRational Intersection_point(const Line& p, const Line& q);

struct Polygon {
	std::vector<Vector2DInt> points;

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

	void Add(const Vector2DInt& point);
	void Reverse();

	int Side_num() const;
	long long Area_twice(bool oriented = false) const;
	bool Is_convex(bool oriented = false) const;
};

struct Triangle {
	Vector2DInt a;
	Vector2DInt b;
	Vector2DInt c;

	Triangle();
	Triangle(const Vector2DInt& a, const Vector2DInt& b, const Vector2DInt& c);
	Triangle(const Triangle&) = default;
	Triangle& operator=(const Triangle&) = default;
private:
	void Reduce();
public:
	long long Area_twice() const;
};

struct Circle {
	Vector2DDouble center;
	double radius;

	Circle();
	Circle(const Vector2DDouble& center, double radius);
	Circle(const Circle&) = default;
	Circle& operator=(const Circle&) = default;
};

Polygon Convex_hull(const std::vector<Vector2DInt>& points_arg);


#endif

#ifdef ONLY_MY_ENVIR
#include "Geometry.h"
#include "Math.h"
#endif

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

/* int に関してはオーバーフローが多くの場所で起こっている */

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

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

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

/*---------------------------------*/
/*--------   Vector2DInt   --------*/
/*---------------------------------*/

Vector2DInt::Vector2DInt()
	: Vector2DInt(0, 0) {
}

Vector2DInt::Vector2DInt(int x, int y)
	: x(x), y(y) {
}

Vector2DInt::Vector2DInt(const std::pair<int, int>& pair)
	: Vector2DInt(pair.first, pair.second) {
}

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

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

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

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

Vector2DInt& Vector2DInt::operator*=(int scalar) {
	x *= scalar;
	y *= scalar;
	return *this;
}

Vector2DInt& Vector2DInt::operator/=(int scalar) {
	x /= scalar;
	y /= scalar;
	return *this;
}

bool Vector2DInt::Is_zero() const {
	return x == 0 && y == 0;
}

long long Vector2DInt::Norm2() const {
	return (long long)x * x + (long long)y * y;
}

double Vector2DInt::Norm() const {
	return std::sqrt(Norm2());
}

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

PolarCoorinates Vector2DInt::To_polar() const {
	return PolarCoorinates(Norm(), Arg());
}

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

int Vector2DInt::Compare(const Vector2DInt& left, const Vector2DInt& 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 Vector2DInt::CompareArg(const Vector2DInt& left, const Vector2DInt& right) {
	/* ゼロベクトルは最も小さいとする */
	if (left.Is_zero()) return right.Is_zero() ? 0 : -1;
	if (right.Is_zero()) return 1;

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

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


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

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

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

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

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

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

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

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

Vector2DInt operator*(const Vector2DInt& vec, int scalar) {
	Vector2DInt ret(vec);
	ret *= scalar;
	return ret;
}

Vector2DInt operator*(int scalar, const Vector2DInt& vec) {
	Vector2DInt ret(vec);
	ret *= scalar;
	return ret;
}

Vector2DRational operator/(const Vector2DInt& vec, int scalar) {
	Vector2DInt ret(vec);
	ret /= scalar;
	return ret;
}

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

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


long long Dot(const Vector2DInt& left, const Vector2DInt& right) {
	return (long long)left.x * right.x + (long long)left.y * right.y;
}

long long Cross(const Vector2DInt& left, const Vector2DInt& right) {
	return (long long)left.x * right.y - (long long)left.y * right.x;
}

bool Is_orthogonal(const Vector2DInt& a, const Vector2DInt& b) {
	return Dot(a, b) == 0;
}

bool Is_parallel(const Vector2DInt& a, const Vector2DInt& b) {
	return Cross(a, b) == 0;
}

/* [-PI, PI] */
Radian Angle(const Vector2DInt& from, const Vector2DInt& center, const Vector2DInt& to) {
	Radian angle = (to - center).Arg() - (from - center).Arg();
	if (angle < 0) angle += 2 * PI;
	return angle;
}

Vector2DDouble Internal(const Vector2DInt& a, const Vector2DInt& b, double ratio) {
	return a * ratio + b * (1 - ratio);
}

/* object を direction 方向に射影 */
Vector2DRational Project(const Vector2DInt& object, const Vector2DInt& direction) {
	return direction * Dot(object, direction) / direction.Norm2();
}

CCWEnum CCW(const Vector2DInt& a, const Vector2DInt& b, const Vector2DInt& p) {
	Vector2DInt ab = b - a;
	Vector2DInt ap = p - a;
	if (Cross(ab, ap) > 0) return CCWEnum::Counterclockwise;
	if (Cross(ab, ap) < 0) return CCWEnum::Clockwise;
	if (Dot(ab, ap) < 0) return CCWEnum::Backward_On_Line;
	if (ab.Norm2() < ap.Norm2()) return CCWEnum::Forward_On_Line;
	return CCWEnum::Internal;
}

/*---------------------------------*/
/*--------   LineSegment   --------*/
/*---------------------------------*/

LineSegment::LineSegment()
	: LineSegment(Vector2DInt(), Vector2DInt()) {
}

LineSegment::LineSegment(const Vector2DInt& point_a, const Vector2DInt& point_b)
	: start(point_a), end(point_b) {
	if (start > end) {
		std::swap(start, end);
	}
}

LineSegment::LineSegment(const std::pair<Vector2DInt, Vector2DInt>& pair)
	: LineSegment(pair.first, pair.second) {
}

int LineSegment::Compare(const LineSegment& left, const LineSegment& right) {
	if (left.start < right.start) return -1;
	if (left.start > right.start) return 1;
	if (left.end < right.end) return -1;
	if (left.end > right.end) return 1;
	return 0;
}

double Distance_segment_vector(const LineSegment& segment, const Vector2DInt& vec) {
	/* start が最も近い */
	if (Dot(segment.end - segment.start, vec - segment.start) <= 0) {
		return (vec - segment.start).Norm();
	}

	/* end が最も近い */
	if (Dot(segment.start - segment.end, vec - segment.end) <= 0) {
		return (vec - segment.end).Norm();
	}

	/* それ以外 → 点と直線の距離 */
	return Distance_line_vector(Line(segment), vec);
}

Vector2DDouble Internal(const LineSegmentDirected& segment, double ratio) {
	return Internal(segment.start, segment.end, ratio);
}

bool Has_Intersection_point(const LineSegment& a, const LineSegment& b) {
	return (int)CCW(a.start, a.end, b.start) * (int)CCW(a.start, a.end, b.end) <= 0
		&& (int)CCW(b.start, b.end, a.start) * (int)CCW(b.start, b.end, a.end) <= 0;
}

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

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

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

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

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

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

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

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

Line::Line(int a, int b, int c)
	: Line(Vector2DInt(a, b), c) {
}

Line::Line(const Vector2DInt& normal, int c)
	: normal(normal), c(c) {
	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 Vector2DInt& p, const Vector2DInt& q)
	: Line(p.y - q.y, q.x - p.x, Cross(p, q)) {
}

Line::Line(const LineSegment& segment)
	: Line(segment.start, segment.end) {
}

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

	/* normal と c の値は既約とする */
	int gcd = GCD(GCD(abs(normal.x), abs(normal.y)), abs(c));
	if (gcd != 1) {
		normal /= gcd;
		c /= gcd;
	}

	/* 0 <= normal.Arg < PI とする */
	if (!normal.Arg_is_less_than_pi()) {
		normal = -normal;
		c = -c;
	}
}

bool Line::Is_on(const Vector2DRational& point) const {
	return Dot(normal, point) + c == 0;
}

Rational Line::value_y_where_x_is(int x) const {
	const int a = normal.x;
	const int b = normal.y;
	return -(a * x + c) / (Rational)b;
}

Rational Line::value_x_where_y_is(int y) const {
	const int a = normal.x;
	const int b = normal.y;
	return -(b * y + c) / (Rational)a;
}

LineSegment Line::To_segment() const {
	assert(0);
	if (normal.y == 0) {
		// x + c == 0
		return LineSegment(Vector2DInt(-c, 0), Vector2DInt(-c, 1));
	}
	return LineSegment(
		Vector2DInt(0, value_y_where_x_is(0)),
		Vector2DInt(1, value_y_where_x_is(1))
		);
}

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.c < right.c) return -1;
	if (left.c > right.c) 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_line_vector(const Line& line, const Vector2DInt& vec) {
	return abs(Dot(line.normal, vec) + line.c) / line.normal.Norm();
}

/* object を direction 方向に射影 */
Vector2DRational Project(const Vector2DInt& object, const Line& direction) {
	return object - Project(object, direction.normal);
}

Vector2DRational Reflect(const Vector2DInt& object, const Line& axis) {
	return object - axis.normal * (Dot(object, axis.normal) + axis.c) / axis.normal.Norm2();
}

LineSegment Reflect(const LineSegment& object, const Line& axis) {
	const Vector2DRational reflected_start = Reflect(object.start, axis);
	const Vector2DRational reflected_end = Reflect(object.end, axis);
	return LineSegment(reflected_start, reflected_end);
}

/* LineSegment 用の関数を使うのがよさそう */
Line Reflect(const Line& object, const Line& axis) {
	assert(0);
	return Line(Reflect(object.To_segment(), axis));
}

Vector2DRational Intersection_point(const Line& p, const Line& q) {
	Vector2DInt vec_a(p.normal.x, q.normal.x);
	Vector2DInt vec_b(p.normal.y, q.normal.y);
	Vector2DInt vec_c(p.c, q.c);
	long long det = Cross(vec_a, vec_b);
	return Vector2DRational(Cross(vec_b, vec_c) / det, (Cross(vec_c, vec_a) / det));
}

bool Has_Intersection_point(const LineSegment& segment, const Line& line) {
	return Sign(Dot(segment.start, line.normal)) * Sign(Dot(segment.end, line.normal)) <= 0;
}

bool Has_Intersection_point(const Line & line, const LineSegment & segment) {
	return Has_Intersection_point(segment, line);
}

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

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

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

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

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

void Polygon::Add(const Vector2DInt& point) {
	points.push_back(point);
}

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

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

long long Polygon::Area_twice(bool oriented) const {
	if (Side_num() <= 2) return 0;
	long long sum = 0;
	Vector2DInt reference = points[0];
	for (int i = 1; i < Side_num() - 1; ++i) {
		sum += Cross(points[i] - reference, points[i + 1] - reference);
	}
	return oriented ? sum : abs(sum);
}

bool Polygon::Is_convex(bool oriented) const {
	const int N = Side_num();
	if (N <= 2) return true;
	
	CCWEnum first_ccw = CCW(points[0], points[1], points[2]);
	if (oriented && first_ccw != CCWEnum::Counterclockwise) return false;
	for (int i = 1; i < N; ++i) {
		const Vector2DInt& a = points[i];
		const Vector2DInt& b = points[(i + 1) % N];
		const Vector2DInt& c = points[(i + 2) % N];
		CCWEnum ccw = CCW(a, b, c);
		if (first_ccw != ccw) return false;
	}
	return true;
}

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

Triangle::Triangle()
	: Triangle(Vector2DInt(), Vector2DInt(), Vector2DInt()) {
}

Triangle::Triangle(const Vector2DInt& a, const Vector2DInt& b, const Vector2DInt& 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);
}

long long Triangle::Area_twice() const {
	return Cross(b - a, c - a);
}

/*---------------------------------*/
/*-----------   Circle   ----------*/
/*---------------------------------*/

Circle::Circle()
	: Circle(Vector2DDouble(), 0){
}

Circle::Circle(const Vector2DDouble& center, double radius)
	: center(center), radius(radius) {
}
/*---------------------------------*/
/*---------   グローバル   --------*/
/*---------------------------------*/

/* 要最適化 */
Polygon Convex_hull(const std::vector<Vector2DInt>& points_arg) {
	std::vector<Vector2DInt> points(points_arg);
	sort(points.begin(), points.end());

	std::vector<Vector2DInt> vertices;
	Polygon ret;

	/* 下側部分を生成 */
	for (auto it = points.begin(); it != points.end(); ++it) {
		while (vertices.size() >= 2
			&& CCW(vertices[vertices.size() - 2], vertices[vertices.size() - 1], *it) != CCWEnum::Counterclockwise) {
			vertices.pop_back();
		}
		vertices.push_back(*it);
	}
	for (auto it = vertices.begin(); it != vertices.end() - 1; ++it) {
		ret.Add(*it);
	}
	vertices.clear();

	/* 上側部分を生成 */
	for (auto rit = points.rbegin(); rit != points.rend(); ++rit) {
		while (vertices.size() >= 2
			&& CCW(vertices[vertices.size() - 2], vertices[vertices.size() - 1], *rit) != CCWEnum::Counterclockwise) {
			vertices.pop_back();
		}
		vertices.push_back(*rit);
	}
	for (auto it = vertices.begin(); it != vertices.end() - 1; ++it) {
		ret.Add(*it);
	}

	return ret;
}
#define _CRT_SECURE_NO_WARNINGS
#define _SCL_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <cstring>
#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>

using namespace std;
typedef unsigned int uint;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL, LL> PP;
#define REP(i,a,n) for(LL i = (a); i < (LL)(n); ++i)
#define REM(i,a,n) for(LL i = ((n) - 1); i >= (a); --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 string INFSTR = "\x7f";
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 Compare(T left, T right) { return left > right ? 1 : (left < right ? -1 : 0); }
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; }
template <class ForwardIterator, class T>
bool All_of(ForwardIterator first, ForwardIterator last, const T& value) {
	for (; first < last; ++first) if (*first != value) return false; return true;
}
// all_of

#ifdef ONLY_MY_ENVIR
#include "IntMod.h"
#include "Union_Find.h"
#include "Graph.h"
#include "Range.h"
#include "Global.h"
#include "Flow_Solver.h"
#include "Tree.h"
#include "Suffix_Array.h"
#include "Geometry.h"
#include "Matrix.h"
#include "Segment_Tree.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

#if 1234567891
#include <array>
#include <random>
#include <unordered_set>
#include <unordered_map>
template<typename T>
using PriorityQ = priority_queue<T, vector<T>, greater<T> >;	// コスト小を優先
#endif

int N;
vector<Vector2DInt> vec;
int main() {
	cin >> N;
	REP(i, 0, N) {
		Vector2DInt v;
		cin >> v;
		vec.push_back(v);
	}

	auto poly = Convex_hull(vec);

	vector<int> idxs;
	for (auto pos : poly.points) {
		REP(i, 0, N) {
			if (pos == vec[i]) {
				idxs.push_back(i);
			}
		}
	}

	vector<Vector2DInt> diffs;
	vector<double> probs;
	REP(i, 0, poly.Side_num()) {
		diffs.push_back(poly.points[(i + 1) % poly.Side_num()] - poly.points[i]);
	}

	int M = poly.Side_num();
	REP(i, 0, M) {
		Radian r = diffs[i].Arg() - diffs[(i + M - 1) % M].Arg();
		probs.push_back((r < 0 ? r + 2 * PI : r) / (2 * PI));
	}

	vector<double> ans(N);
	REP(i, 0, probs.size()){
		ans[idxs[i]] = probs[i];
	}

	for (double d : ans) {
		cout << FLOAT << d << endl;
	}

	return 0;
}


Compiler output:
a.cc: In function 'uint64_t GCD(const std::vector<long unsigned int>&)':
a.cc:186:62: error: unable to find numeric literal operator 'operator""Ui64'
  186 |         return std::accumulate(values.begin(), values.end(), 0Ui64, (FuncType)GCD);
      |                                                              ^~~~~
a.cc: In function 'uint64_t LCM(const std::vector<long unsigned int>&)':
a.cc:191:62: error: unable to find numeric literal operator 'operator""Ui64'
  191 |         return std::accumulate(values.begin(), values.end(), 1Ui64, (FuncType)LCM);
      |                                                              ^~~~~