Problem:


Score : 600 points

Problem Statement

There are N holes in a two-dimensional plane. The coordinates of the i-th hole are (x_i,y_i).

Let R=10^{10^{10^{10}}}. Ringo performs the following operation:

Randomly choose a point from the interior of a circle of radius R centered at the origin, and put Snuke there. Snuke will move to the hole with the smallest Euclidean distance from the point, and fall into that hole. If there are multiple such holes, the hole with the smallest index will be chosen.

For every i (1 \leq i \leq N), find the probability that Snuke falls into the i-th hole.

Here, the operation of randomly choosing a point from the interior of a circle of radius R is defined as follows:

Pick two real numbers x and y independently according to uniform distribution on [-R,R].

If x^2+y^2\leq R^2, the point (x,y) is chosen. Otherwise, repeat picking the real numbers x,y until the condition is met.

Constraints

2 \leq N \leq 100

|x_i|,|y_i| \leq 10^6(1\leq i\leq N)

All given points are pairwise distinct.

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print N real numbers. The i-th real number must represent the probability that Snuke falls into the i-th hole.

The output will be judged correct when, for all output values, the absolute or relative error is at most 10^{-5}.

Sample Input 1

2
0 0
1 1

Sample Output 1

0.5
0.5

If Ringo put Snuke in the region x+y\leq 1, Snuke will fall into the first hole. The probability of this happening is very close to 0.5.
Otherwise, Snuke will fall into the second hole, the probability of which happening is also very close to 0.5.

Sample Input 2

5
0 0
2 8
4 5
2 6
3 10

Sample Output 2

0.43160120892732328768
0.03480224363653196956
0.13880483535586193855
0.00000000000000000000
0.39479171208028279727



Sample input:
2
0 0
1 1


Sample output:
0.5
0.5

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

const double eps = 1e-10;
inline bool eq(double a, double b) { return fabs(a - b) < eps; }
const double pi = acos(-1);

struct Point {
    double x, y;
    Point() {}
    Point(double x, double y) : x(x), y(y) {}
    Point operator+(const Point &p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point &p) const { return Point(x - p.x, y - p.y); }
    Point operator*(double k) const { return Point(x * k, y * k); }
    Point operator/(double k) const { return Point(x / k, y / k); }
};
istream &operator>>(istream &is, Point &p) {
    is >> p.x >> p.y;
    return is;
}
ostream &operator<<(ostream &os, Point p) {
    os << fixed << setprecision(10) << p.x << " " << p.y;
    return os;
}
bool sort_x(Point a, Point b) { return a.x != b.x ? a.x < b.x : a.y < b.y; }
bool sort_y(Point a, Point b) { return a.y != b.y ? a.y < b.y : a.x < b.x; }
bool sort_t(Point a, Point b) { return atan2(a.y, a.x) < atan2(b.y, a.y); }
Point rotate(double theta, const Point &p) {
    return Point(cos(theta) * p.x - sin(theta) * p.y, sin(theta) * p.x + cos(theta) * p.y);
}
double radian_to_degree(double r) { return (r * 180.0 / pi); }
double degree_to_radian(double d) { return (d * pi / 180.0); }
double get_angle(const Point &a, const Point &b, const Point &c) {
    const Point v(b - a), w(c - b);
    double alpha = atan2(v.y, v.x), beta = atan2(w.y, w.x);
    if (alpha > beta)
        swap(alpha, beta);
    double theta = (beta - alpha);
    return min(theta, 2 * acos(-1) - theta);
}

struct Line {
    Point a, b;
    Line() {}
    Line(Point a, Point b) : a(a), b(b) {}
    Line(double A, double B, double C) { // Ax + By = C
        if (eq(A, 0))
            a = Point(0, C / B), b = Point(1, C / B);
        else if (eq(B, 0))
            a = Point(C / A, 0), b = Point(C / A, 1);
        else
            a = Point(0, C / B), b = Point(C / A, 0);
    }
    Point vec() const { return b - a; }
};
struct Segment : Line {
    Segment() {}
    Segment(Point a, Point b) : Line(a, b) {}
};

struct Circle {
    Point p;
    double r;
    Circle() {}
    Circle(Point p, double r) : p(p), r(r) {}
};
double norm(const Point &a) { return a.x * a.x + a.y * a.y; }
double abs(const Point &a) { return sqrt(norm(a)); }
double cross(const Point &a, const Point &b) { return a.x * b.y - a.y * b.x; }
double dot(const Point &a, const Point &b) { return a.x * b.x + a.y * b.y; }

Point project(Line l, Point p) {
    double t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
    return l.a + (l.a - l.b) * t;
}
Point reflect(Line l, Point p) { return p + (project(l, p) - p) * 2; }
bool parallel(Line a, Line b) { return eq(cross(a.vec(), b.vec()), 0.0); }
bool orthogonal(Line a, Line b) { return eq(dot(a.vec(), b.vec()), 0.0); }
int ccw(const Point &a, Point b, Point c) {
    b = b - a, c = c - a;
    if (cross(b, c) > eps)
        return +1; // "COUNTER_CLOCKWISE"
    if (cross(b, c) < -eps)
        return -1; // "CLOCKWISE"
    if (dot(b, c) < 0)
        return +2; // "ONLINE_BACK"
    if (norm(b) < norm(c))
        return -2; // "ONLINE_FRONT"
    return 0;      // "ON_SEGMENT"
}
bool intersect(const Line &l, const Point &p) { return abs(ccw(l.a, l.b, p)) != 1; }
bool intersect(const Line &l, const Line &m) { return !parallel(l, m) || abs(cross(l.vec(), m.b - l.a)) < eps; }
bool intersect(const Segment &s, const Point &p) { return ccw(s.a, s.b, p) == 0; }
bool intersect(const Line &l, const Segment &s) { return cross(l.vec(), s.a - l.a) * cross(l.vec(), s.b - l.a) < eps; }
double distance(const Line &l, const Point &p);
bool intersect(const Circle &c, const Line &l) { return distance(l, c.p) <= c.r + eps; }
bool intersect(const Circle &c, const Point &p) { return abs(abs(p - c.p) - c.r) < eps; }
bool intersect(const Segment &s, const Segment &t) {
    return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 && ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}
int intersect(const Circle &c, const Segment &l) {
    if (norm(project(l, c.p) - c.p) - c.r * c.r > eps)
        return 0;
    auto d1 = abs(c.p - l.a), d2 = abs(c.p - l.b);
    if (d1 < c.r + eps && d2 < c.r + eps)
        return 0;
    if ((d1 < c.r - eps && d2 > c.r + eps) || (d1 > c.r + eps && d2 < c.r - eps))
        return 1;
    const Point h = project(l, c.p);
    if (dot(l.a - h, l.b - h) < 0)
        return 2;
    return 0;
}
int intersect(Circle c1, Circle c2) {
    if (c1.r < c2.r)
        swap(c1, c2);
    double d = abs(c1.p - c2.p);
    if (c1.r + c2.r < d)
        return 4; // do not cross
    if (eq(c1.r + c2.r, d))
        return 3; // circumscribed
    if (c1.r - c2.r < d)
        return 2; // intersect
    if (eq(c1.r - c2.r, d))
        return 1; // inscribed
    return 0;     // one circle includes another
}

double distance(const Point &a, const Point &b) { return abs(a - b); }
double distance(const Line &l, const Point &p) { return abs(p - project(l, p)); }
double distance(const Line &l, const Line &m) { return intersect(l, m) ? 0 : distance(l, m.a); }
double distance(const Segment &s, const Point &p) {
    Point r = project(s, p);
    if (intersect(s, r))
        return abs(r - p);
    return min(abs(s.a - p), abs(s.b - p));
}
double distance(const Segment &a, const Segment &b) {
    if (intersect(a, b))
        return 0;
    return min({distance(a, b.a), distance(a, b.b), distance(b, a.a), distance(b, a.b)});
}
double distance(const Line &l, const Segment &s) {
    if (intersect(l, s))
        return 0;
    return min(distance(l, s.a), distance(l, s.b));
}
Point crosspoint(const Line &l, const Line &m) {
    double A = cross(l.vec(), m.vec());
    double B = cross(l.vec(), l.b - m.a);
    if (eq(abs(A), 0.0) && eq(abs(B), 0.0))
        return m.a;
    return m.a + (m.b - m.a) * B / A;
}
Point crosspoint(const Segment &l, const Segment &m) { return crosspoint(Line(l), Line(m)); }
pair<Point, Point> crosspoint(const Circle &c, const Line l) {
    Point pr = project(l, c.p);
    Point e  = (l.b - l.a) / abs(l.b - l.a);
    if (eq(distance(l, c.p), c.r))
        return {pr, pr};
    double base = sqrt(c.r * c.r - norm(pr - c.p));
    return {pr - e * base, pr + e * base};
}
pair<Point, Point> crosspoint(const Circle &c, const Segment &l) {
    Line aa = Line(l.a, l.b);
    if (intersect(c, l) == 2)
        return crosspoint(c, aa);
    auto ret = crosspoint(c, aa);
    if (dot(l.a - ret.first, l.b - ret.first) < 0)
        ret.second = ret.first;
    else
        ret.first = ret.second;
    return ret;
}
pair<Point, Point> crosspoint(const Circle &c1, const Circle &c2) {
    double d = abs(c1.p - c2.p);
    double a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d));
    double t = atan2(c2.p.y - c1.p.y, c2.p.x - c1.p.x);
    Point p1 = c1.p + Point(cos(t + a) * c1.r, sin(t + a) * c1.r);
    Point p2 = c1.p + Point(cos(t - a) * c1.r, sin(t - a) * c1.r);
    return {p1, p2};
}
vector<Point> convex_hull(vector<Point> &p) {
    int n = (int)p.size(), k = 0;
    if (n <= 2)
        return p;
    sort(p.begin(), p.end(), sort_x);
    vector<Point> ch(2 * n);
    for (int i = 0; i < n; ch[k++] = p[i++]) {
        while (k >= 2 && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < -eps)
            --k;
    }
    for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]) {
        while (k >= t && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < -eps)
            --k;
    }
    ch.resize(k - 1);
    return ch;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<Point> p(n);
    map<pair<int, int>, int> idx;
    for (int i = 0; i < n; ++i) {
        double x, y;
        cin >> x >> y;
        idx[{x, y}] = i;
        p[i]        = {x, y};
    }
    vector<double> ret(n, 0.0);
    p = convex_hull(p);
    p.push_back(p[0]);
    p.push_back(p[1]);
    for (int i = 1; i < (int)p.size() - 1; ++i) {
        double angle               = get_angle(p[i - 1], p[i], p[i + 1]);
        ret[idx[{p[i].x, p[i].y}]] = angle / (2 * pi);
    }
    for (auto &r : ret) {
        cout << fixed << setprecision(10) << r << "\n";
    }
    return 0;
}

Submission status: Runtime Error

Solution code:
package main

import (
  "bufio"
  "os"
  "strconv"
  "strings"
  "fmt"
  "math"
)

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt() int {
  n, _ := strconv.Atoi(NextLine())
  return n
}
func NextFloatVec() []float64 {
  L := strings.Split(NextLine(), " ")
  N := make([]float64, len(L))
  for i := range N {
    N[i], _ = strconv.ParseFloat(L[i], 64)
  }
  return N
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func Output() {
  _ = writer.Flush()
}

func Dist(mode int, A ...*[]float64) float64 {
  if len(A) < 1 { return 0.0 }
  if len(A) < 2 { A = append(A, &[]float64{0.0, 0.0}) }
  D := 0.0
  for i := range (*A[0]) {
    x := (*A[0])[i] - (*A[1])[i]
    D += x * x
  }
  if mode == 1 { D = math.Sqrt(D) }
  return D
}
func InnerProduct(A, B *[]float64) float64 {
  IP := 0.0
  for i, a := range (*A) {
    IP += a * (*B)[i]
  }
  return IP
}
func Angle(A ...*[]float64) float64 {
  if len(A) < 2 { return 0.0 }
  if len(A) < 3 {
    a := make([]float64, len((*A[0])))
    A = append(A, &a)
  }
  _A := make([]float64, len((*A[0])))
  _B := make([]float64, len((*A[0])))
  for i := range (*A[0]) {
    _A[i] = (*A[0])[i] - (*A[2])[i]
    _B[i] = (*A[1])[i] - (*A[2])[i]
  }
  acos := math.Acos(InnerProduct(&_A, &_B) / Dist(1, &_A) / Dist(1, &_B))
  theta := acos / math.Pi * 180.0
  _A_ := []float64{-_A[1], _A[0]}
  if InnerProduct(&_A_, &_B) < 0 { theta = 360 - theta }
  return theta
}
func TriangleArea(mode int, A ...*[]float64) float64 {
  if len(A) < 2 { return 0.0 }
  if len(A) < 3 {
    _A := make([]*[]float64, 0)
    a := make([]float64, len((*A[0])))
    _A = append(_A, &a)
    A = append(_A, A...)
  }
  AB := []float64{(*A[1])[0] - (*A[0])[0], (*A[1])[1] - (*A[0])[1]}
  AC := []float64{(*A[2])[0] - (*A[0])[0], (*A[2])[1] - (*A[0])[1]}
  S := math.Abs(AB[0] * AC[1] - AB[1] * AC[0])
  if mode == 1 { S /= 2.0 }
  return S
}
func OuterCircle(A, B, C *[]float64) (X, Y, R float64) {
  AB := []float64{(*B)[0] - (*A)[0], (*B)[1] - (*A)[1]}
  AC := []float64{(*C)[0] - (*A)[0], (*C)[1] - (*A)[1]}
  AB2 := Dist(2, &AB)
  AC2 := Dist(2, &AC)
  IP := InnerProduct(&AB, &AC)
  b := AC2 * (IP - AB2) / (2 * (IP * IP - AB2 * AC2))
  c := AB2 * (IP - AC2) / (2 * (IP * IP - AB2 * AC2))
  X = (*A)[0] + AB[0] * b + AC[0] * c
  Y = (*A)[1] + AB[1] * b + AC[1] * c
  S := TriangleArea(1, A, B, C)
  ab := math.Sqrt(AB2)
  bc := Dist(1, B, C)
  ca := math.Sqrt(AC2)
  R = ab * bc * ca / (4 * S)
  return
}
func Less(A *[][]float64, i, j int) bool {
  if (*A)[i][0] == (*A)[j][0] { return (*A)[i][1] < (*A)[j][1] }
  return (*A)[i][0] < (*A)[j][0]
}
func Convex(A *[][]float64) []int {
  C := make([]int, 0)
  h := 0
  for i := range (*A) {
    if Less(A, h, i) { h = i }
  }
  next := h
  for len(C) == 0 || next != h {
    C = append(C, next)
    p := (*A)[next]
    for i, a := range (*A) {
      if i == next { continue }
      _A := []float64{a[0] - p[0], a[1] - p[1]}
      D1 := Dist(2, &a, &p)
      convex := true
      for j, b := range (*A) {
        if j == next || j == i { continue }
        _B := []float64{b[0] - p[0], b[1] - p[1]}
        D2 := Dist(2, &b, &p)
        OP := _A[0] * _B[1] - _A[1] * _B[0]
        if math.Abs(OP) < 1e-5 {
          if D2 < D1 { continue }
        } else if OP < 0.0 {
          continue
        }
        convex = false
        break
      }
      if !convex { continue }
      next = i
      break
    }
  }
  return C
}

func Solve() {
  N := NextInt()
  A := make([][]float64, N)
  for i := range A {
    A[i] = NextFloatVec()
  }
  C := Convex(&A)
  C = append(C, C...)
  R := make([]float64, N)
  for i := 0; i < len(C) / 2; i++ {
    if C[i] == C[i + 2] {
      R[C[i + 1]] = 180.0
      continue
    }
    x, y, _ := OuterCircle(&A[C[i]], &A[C[i + 1]], &A[C[i + 2]])
    _A := []float64{A[C[i + 2]][0] - x, A[C[i + 2]][1] - y}
    _B := []float64{A[C[i]][0] - x, A[C[i]][1] - y}
    theta := Angle(&_A, &_B)
    R[C[i + 1]] = theta / 2.0
  }
  for _, r := range R {
    Write(r / 360.0)
  }
  return
}

func main() {
  Solve()
  Output()
}

Submission status: Runtime Error

Solution code:
import cmath
import math
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def det(a: complex, b: complex):
    # 外積
    return a.real * b.imag - a.imag * b.real


def graham_scan(points):
    """
    凸包
    :param list of complex|np.ndarray points:
    :rtype: list of complex
    """
    if len(points) <= 2:
        return list(points)
    points = np.sort_complex(points)
    # Graham Scan
    sz = 0
    #: :type: list of (complex|None)
    ret = [None] * N
    for p in points:
        while sz > 1 and det(ret[sz - 1] - ret[sz - 2], p - ret[sz - 1]) <= 0:
            sz -= 1
        ret[sz] = p
        sz += 1
    floor = sz
    for p in reversed(points[:-1]):
        while sz > floor and det(ret[sz - 1] - ret[sz - 2], p - ret[sz - 1]) <= 0:
            sz -= 1
        ret[sz] = p
        sz += 1
    ret = ret[:sz - 1]
    return ret


N = int(sys.stdin.buffer.readline())
X, Y = list(zip(*[map(int, sys.stdin.buffer.readline().split()) for _ in range(N)]))
TAU = math.pi * 2

if N == 2:
    print(0.5)
    print(0.5)
    exit()

points = [complex(x, y) for x, y in zip(X, Y)]
pos = {p: i for i, p in enumerate(points)}

# 凸包
points = graham_scan(points)
points = np.array(points, dtype=complex)

# 中心からの角度でソート
center = points.mean()
idx = np.angle(points - center).argsort()
points = points[idx]

ans = [0.0] * N
for i in range(len(points)):
    pr = points[(i + 1) % len(points)]
    p = points[i]
    pl = points[(i - 1) % len(points)]

    # 凸包の内側から、頂点の両隣の辺に垂線をおろしたときの角度
    # pi - 角度
    ans[pos[p]] += (math.pi - (cmath.phase(pl - p) - cmath.phase(pr - p)) % TAU) / TAU

if ans:
    print(*ans, sep='\n')

# from matplotlib import pyplot as plt
#
# points -= center
# theta = [cmath.phase(p) for p in points]
# r = [abs(p) for p in points]
#
# fig = plt.figure()
# ax = fig.add_subplot(111, projection='polar')
# ax.scatter(theta, r, s=max(r))
# plt.show()

Submission status: Runtime Error

Solution code:
from scipy.spatial import ConvexHull as CH
import numpy as np
norm=np.linalg.norm
n,*t=map(int,open(0).read().split())
a=np.reshape(t,(n,2))
h=CH(a).vertices
l=len(h)
for i in range(n):
	if i in h:
		j=np.where(h==i)[0]
		f,s,t=a[h[j-1]],a[i],a[h[(j+1)%l]]
		print(np.arccos(np.inner(t-s,s-f)/(norm(t-s)*norm(s-f)))[0,0]/(2*np.pi))
	else:
		print(0.)

Submission status: Runtime Error

Solution code:
import math

n = int(input())
a = []
b = []

for _ in range(n):
    x,y = map(int,input().split())
    a.append([x,y])
    b.append([x,y])

#引用 https://qiita.com/kkttm530/items/d6ca372491b75baeac3c
def signed_area(p1, p2, p3):
    '''符号付き面積を計算 '''

    area = (((p2[0] - p1[0]) * (p3[1] - p1[1])) - ((p3[0] - p1[0]) * (p2[1] - p1[1]))) / 2
    return area


def convex_hull(p_list):
    '''グラハムの凸包走査 '''

    p_sort = []
    for i in p_list:
        p_sort.append(i[0])

    # x座標が最小のものをリストの先頭に配置。
    min_index = p_sort.index(min(p_sort))
    min_p = p_list.pop(min_index)
    p_list.insert(0, min_p)

    # 座標最小の点と他の点との角度順にソート ソートアルゴリズムに選択の余地が有る。
    p_length = len(p_list)
    count = 0
    index = 0
    while True:
        count += 1
        index += 1

        area_sign = signed_area(p_list[0], p_list[index], p_list[index + 1])

        # 符号付き面積が負ならば点を入れ替え
        if area_sign < 0:
            p_list[index], p_list[index + 1] = p_list[index + 1], p_list[index]
            count = 0

        if count == p_length - 1:
            break

        if index == p_length - 2:
            index = 0

    # 凹部の点を削除する。
    index = -1
    count = 0
    while True:
        index += 1
        count += 1

        area_sign = signed_area(p_list[index], p_list[index + 1], p_list[index + 2])
        if area_sign < 0:
            del p_list[index + 1]
            count = 0

        if count == len(p_list):
            break

        if index >= len(p_list) - 3:
            index = -1
    return p_list

p = convex_hull(a)
rad = [0]*len(p)

for i in range(len(p)):
    rad[i-1] = 180 - math.degrees(math.atan2(p[i-2][1]-p[i-1][1],p[i-2][0]-p[i-1][0])) + math.degrees(math.atan2(p[i][1]-p[i-1][1],p[i][0]-p[i-1][0]))
    if rad[i-1] >= 360:
        rad[i-1] -= 360

for i in range(n):
    if b[i] not in p:
        print(0)
    else:
        for j in range(len(p)):
            if p[j] == b[i]:
                print(rad[j]/360)

Submission status: Runtime Error

Solution code:
import sys
import math
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))

N = int(input())
point = []
for _ in range(N):
    point.append(inpl())
xg = sum(point[i][0] for i in range(N))/N
yg = sum(point[i][1] for i in range(N))/N
for i in range(N):
    x, y = point[i]
    x -= xg
    y -= yg
    r = math.hypot(x,y)
    th = math.atan2(y,x)
    point[i] = [r,th,0,i]
point.sort(key=lambda x:x[1])
R = [ point[i][0] for i in range(N) ]
start = R.index(max(R))

nxt = start
while True:
    cur = nxt
    rc, thc = point[cur][:2]
    m = 0
    i = cur
    while True:
        i = (i+1) % N
        ri, thi = point[i][:2]
        dth = (thi - thc) % (math.pi*2)
        if dth > math.pi or i==cur: break
        ell = math.sqrt(rc*rc + ri*ri - 2*rc*ri*math.cos(dth))
        cos_alpha = (rc*rc + ell*ell - ri*ri)/(2*rc*ell)
        sin_alpha = ri*math.sin(dth)/ell
        alpha = math.acos(cos_alpha)
        if sin_alpha > m:
            m = sin_alpha
            nxt = i
            alpha_nxt = alpha
    point[cur][2] += math.pi/2 - alpha_nxt + thc
    point[nxt][2] -= math.pi/2 - alpha_nxt + thc
    if nxt == start: break

point.sort(key=lambda x:x[3])
for i in range(N):
    print((point[i][2]/(2*math.pi))%1)

Submission status: Runtime Error

Solution code:
import math
pi=3.141592657589793238462643383279

#quoted from https://qiita.com/kkttm530/items/d6ca372491b75baeac3c
def signed_area(p1, p2, p3):
    '''符号付き面積を計算 '''

    area = (((p2[0] - p1[0]) * (p3[1] - p1[1])) - ((p3[0] - p1[0]) * (p2[1] - p1[1]))) / 2
    return area


def convex_hull(p_list):
    '''グラハムの凸包走査 '''

    p_sort = []
    for i in p_list:
        p_sort.append(i[0])

    # x座標が最小のものをリストの先頭に配置。
    min_index = p_sort.index(min(p_sort))
    min_p = p_list.pop(min_index)
    p_list.insert(0, min_p)

    # 座標最小の点と他の点との角度順にソート ソートアルゴリズムに選択の余地が有る。
    p_length = len(p_list)
    count = 0
    index = 0
    while True:
        count += 1
        index += 1

        area_sign = signed_area(p_list[0], p_list[index], p_list[index + 1])

        # 符号付き面積が負ならば点を入れ替え
        if area_sign < 0:
            p_list[index], p_list[index + 1] = p_list[index + 1], p_list[index]
            count = 0

        if count == p_length - 1:
            break

        if index == p_length - 2:
            index = 0

    # 凹部の点を削除する。
    index = -1
    count = 0
    while True:
        index += 1
        count += 1

        area_sign = signed_area(p_list[index], p_list[index + 1], p_list[index + 2])
        if area_sign < 0:
            del p_list[index + 1]
            count = 0

        if count == len(p_list):
            break

        if index >= len(p_list) - 3:
            index = -1
    return p_list

def getVectorLength(x,y):
  return (x**2+y**2)**0.5

def dotProduct(u,v):
  return u[0]*v[0]+u[1]*v[1]

def vectorsAngle(u,v):
  l1=getVectorLength(u[0],u[1])
  l2=getVectorLength(v[0],v[1])
  cosTheta=dotProduct(u,v)/(l1*l2)
  theta=math.acos(cosTheta)
  return 180*theta/pi
  
n=int(input())
arr=[]
for _ in range(n):
  x,y=map(int,input().split())
  arr.append((x,y))
arr2=convex_hull(arr[:])
ans=[0]*n
if n==2:
  print(0.5)
  print(0.5)
else:
  for i in range(n):
    pos=arr[i]
    if pos not in arr2:
      continue
    else:
      idx=arr2.index(pos)
      pos1=arr2[idx-1]
      pos2=arr2[(idx+1)%len(arr2)]
      x1=pos[0]-pos1[0]
      y1=pos[1]-pos1[1]
      x2=pos2[0]-pos[0]
      y2=pos2[1]-pos[1]
      angle=math.atan2(x1*y2-x2*y1,x1*x2+y1*y2)
      ans[i]=angle/(2*pi)
  for i in range(n):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import math
n=int(input())
a=[list(map(int,input().split()))for i in range(n)]
b=[[-360,360]for i in range(n)]
for i in range(n):
    d=b[i]
    for j in range(n):
        if i!=j:
            if a[j][1]-a[i][1]==0:
                s=90
            else:
                s=math.degrees(atan((a[i][0]-a[j][0])/(a[j][1]-a[i][1])))
            if a[j][1]-a[i][1]<0:
                d[0]=max(d[0],s)
                d[1]=min(d[1],180+s)
            else:
                if s>0:
                    d[0]=max(d[0],-180+s)
                    d[1]=min(d[1],s)
                else:
                    d[0]=max(d[0],180+s)
                    d[1]=min(d[1],360+s)
for i in range(n):
    if b[i][0]<b[i][1]:
        if b[i][0]<0 and b[i][0]+360<b[i][1]:
            print((b[i][1]-b[i][0]-360)/360)
        else:
            k=(b[i][1]-b[i][0])/360
            print(k)
    else:
        print(0)

Submission status: Runtime Error

Solution code:
import math
n=int(input())
a=[list(map(int,input().split()))for i in range(n)]
b=[[-360,360]for i in range(n)]
for i in range(n):
    d=b[i]
    for j in range(n):
        if i!=j:
            if a[j][1]-a[i][1]==0:
                s=90
            else:
                s=math.degrees(atan((a[i][0]-a[j][0])/(a[j][1]-a[i][1])))
            if a[j][1]-a[i][1]<0:
                d[0]=max(d[0],s)
                d[1]=min(d[1],180+s)
            else:
                if s>0:
                    d[0]=max(d[0],-180+s)
                    d[1]=min(d[1],s)
                else:
                    d[0]=max(d[0],180+s)
                    d[1]=min(d[1],360+s)
for i in range(n):
    if b[i][0]<b[i][1]:
        if b[i][0]<0 and b[i][0]+360<b[i][1]:
            print(0)
        else:
            k=(b[i][1]-b[i][0])/360
            print(k)
    else:
        print(0)

Submission status: Runtime Error

Solution code:
#021-B
import sys
input=sys.stdin.readline
from math import atan2,pi
from operator import itemgetter

def InnerProduct(V0,V1):
    x0,y0=V0
    x1,y1=V1
    return x0*x1+y0*y1
def CrossProduct(V0,V1):
    x0,y0=V0
    x1,y1=V1
    return x0*y1-x1*y0
def angle(P0,P1):
    x0,y0=P0
    x1,y1=P1
    return atan2(y1-y0,x1-x0)
def counterclockwise(P0,P1,P2):
    V0,V1=(P1[0]-P0[0],P1[1]-P0[1]),(P2[0]-P0[0],P2[1]-P0[1])
    return CrossProduct(V0,V1)>0

def GrahamScan(P):
    V=sorted(P,key=itemgetter(1))
    V0=V[0]
    V=sorted(V[1:], key=lambda p: angle(p,V0))+V[:1]
    convex=V[-1:]+V[:1]
    last_x,last_y=convex[-1]
    for p in V[1:]:
        while not counterclockwise(convex[-2],convex[-1],p):
            convex.pop()
        convex.append(p)
        last_x,last_y=p
    return convex[:-1]

n=int(input())
P=[tuple(map(int,input().split())) for _ in range(n)]
d={p: i for i,p in enumerate(P)}
ans=[0]*n
CH=GrahamScan(P)*2
for (x0,y0),(x1,y1),(x2,y2) in zip(CH,CH[1:],CH[2:]):
    V0,V1=(x0-x1,y0-y1),(x2-x1,y2-y1)
    ans[d[(x1,y1)]]=(pi+atan2(CrossProduct(V0,V1),InnerProduct(V0,V1)))/(2*pi)
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
import math

n = int(input())
c = [[0]*2 for i in range(n) ]
a = [0] * n
p = math.pi
for i in range(n):
    c[i][0], c[i][1] = map(float, input().split())

def f(ax, ay, bx, by, cx, cy):
    vx = ax - cx
    vy = ay - cy
    wx = bx - cx
    wy = by - cy
    s = 1
    if vx * wy - vy * wx < 0: s = -1
    p = vx * wx + vy * wy
    q = ( vx * vx + vy * vy ) ** 0.5
    r = ( wx * wx + wy * wy ) ** 0.5
    t = p / (q * r)
    t = max(-1, min(1, t))
    t = (math.acos( p / (q * r) )) * s
    return t

for i in range(n):
    k = (i+1)%n
    tax = 0
    tin = 0
    for j in range(n):
        if j != i and j != k:
            t = f(c[k][0], c[k][1], c[j][0], c[j][1], c[i][0], c[i][1])
            tax = max(tax, t)
            tin = min(tin, t)
    if tax - tin < p:
        a[i] = (p - tax + tin) / (p * 2)

for i in range(n):
    print(round(a[i], 6))

Submission status: Runtime Error

Solution code:
import math

n = int(input())
c = [[0]*2 for i in range(n) ]
a = [0] * n
p = math.pi
for i in range(n):
    c[i][0], c[i][1] = map(float, input().split())

def f(ax, ay, bx, by, cx, cy):
    vx = ax - cx
    vy = ay - cy
    wx = bx - cx
    wy = by - cy
    s = 1
    if vx * wy - vy * wx < 0: s = -1
    p = vx * wx + vy * wy
    q = ( vx * vx + vy * vy ) ** 0.5
    r = ( wx * wx + wy * wy ) ** 0.5
    t=0
    t = (math.acos( p / (q * r) )) * s
    return t

for i in range(n):
    k = (i+1)%n
    tax = 0
    tin = 0
    for j in range(n):
        if j != i and j != k:
            t = f(c[k][0], c[k][1], c[j][0], c[j][1], c[i][0], c[i][1])
            tax = max(tax, t)
            tin = min(tin, t)
    if tax - tin < p:
        a[i] = (p - tax + tin) / (p * 2)

for i in range(n):
    print(a[i])

Submission status: Runtime Error

Solution code:
import math
import sys
def cross(a, b):
	return a[0]*b[1]-a[1]*b[0]
def dot(a, b):
	return a[0]*b[0]+a[1]*b[1]
def counterclockwise(a, b):
	return cross(a, b)<0
def sub(a, b):
	return [a[0]-b[0], a[1]-b[1]]
n=input()
p=[map(int, raw_input().split()) for i in range(n)]
index={tuple(p[i]): i for i in range(n)}
p.sort()
hull=[p[0]]
min_size=1
for i in range(1, n):
	while len(hull)>min_size and not counterclockwise(sub(p[i], hull[-1]), sub(hull[-1], hull[-2])):
		del hull[-1]
	hull.append(p[i])
assert hull[-1]==p[-1]
min_size=len(hull)
for i in range(n-2, -1, -1):
	while len(hull)>min_size and not counterclockwise(sub(p[i], hull[-1]), sub(hull[-1], hull[-2])):
		del hull[-1]
	hull.append(p[i])
assert hull[0]==hull[-1]==p[0]
del hull[-1]
result=[0.0]*n
print>>sys.stderr, hull
for i in range(len(hull)):
	a=sub(hull[(i+1)%len(hull)], hull[i])
	b=sub(hull[i], hull[i-1])
	angle=math.acos(dot(a, b)/math.sqrt(dot(a, a))/math.sqrt(dot(b, b)))
	result[index[tuple(hull[i])]]=angle
for i in range(n):
	print result[i]/math.pi/2, 
print

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from math import acos

def ccw(p1,p2,p3):
    return (p2[0]-p1[0])*(p3[1]-p1[1]) - (p2[1]-p1[1])*(p3[0]-p1[0])

def ConvexHull(points):
    u = []
    l = []
    points.sort()
    
    for p in points:
        while len(u)>1 and ccw(u[-2], u[-1], p)>=0:
            u.pop()
        while len(l)>1 and ccw(l[-2], l[-1], p)<=0:
            l.pop()
            
        u.append(p)
        l.append(p)
        
    return u + l[-2:0:-1]


def angle(v1, v2):
    inner = v1[0]*v2[0] + v1[1]*v2[1]
    normv1 = (v1[0]**2 + v1[1]**2) ** 0.5
    normv2 = (v2[0]**2 + v2[1]**2) ** 0.5
    
    return acos(inner / (normv1*normv2))

n = ni()
if n == 1:
    print(1)

elif n == 2:
    print(0.5)
    print(0.5)
    
else:
    points = [list(li()) + [i] for i in range(n)]    
    ch = ConvexHull(points)    
    bsc = []
    
    for i in range(len(ch)):
        x1,y1,i1 = ch[i]
        x2,y2,i2 = ch[i-1]
        
        bsc.append((y1-y2, x2-x1))
        
    if len(ch) == 2:
        angles = [1,1]
        
    else:
        angles = [angle(bsc[i], bsc[i-1]) for i in range(len(ch))]
        sm = sum(angles)
        
    ans = [0]*n
    for i in range(len(ch)):
        x,y,ind = ch[i-1]
        ans[ind] = angles[i] / sm
        
    for x in ans:
        print(x)

Submission status: Runtime Error

Solution code:
from math import sqrt,pi,acos
n = int(input())
p1 = [[int(i) for i in input().split()] for i in range(n)]
p,q,ans = sorted(p1),[],[]
x1,x2,y1,y2,z1,z2 = p[0][0],p[0][1]+1,p[0][0],p[0][1],10**6+1,0
def cos(a,b,c,d,e,f):
	a,b,e,f = a-c,b-d,e-c,f-d
	return (a*e+b*f)/(sqrt(a**2+b**2)*sqrt(e**2+f**2))
while p[0]!=[z1,z2]:
	q.append([y1,y2])
	num = 2
	for i,j in p:
		if y1!=i or y2!=j:
			m = cos(x1,x2,y1,y2,i,j)
			if num>m: num,z1,z2 = m,i,j
	ans.append((pi-acos(num))/(2*pi))
	x1,x2,y1,y2 = y1,y2,z1,z2
ans = [(pi-acos(cos(x1,x2,y1,y2,q[1][0],q[1][1])))/(2*pi)]+ans[1:]
for i in p1:
	if i in q: print(ans[q.index(i)])
	else: print(0)