Submission #9461036

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
# 2点の直径または3点の外心をテスト
import itertools
import numpy as np
N = int(readline())
m = map(int,read().split())
Z = [x + y * 1j for x,y in zip(m,m)]
def find_O(z0,z1,z2):
    z1 -= z0; z2 -= z0
    if abs((z1 * z2.conjugate()).imag) < 0.5:
        # 同一直線上
        return None
    num = z1 * z2 * (z1-z2).conjugate()
    den = z1.conjugate() * z2
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# 2点の直径または3点の外心をテスト

import itertools
import numpy as np

N = int(readline())
m = map(int,read().split())
Z = [x + y * 1j for x,y in zip(m,m)]

def find_O(z0,z1,z2):
    z1 -= z0; z2 -= z0
    if abs((z1 * z2.conjugate()).imag) < 0.5:
        # 同一直線上
        return None
    num = z1 * z2 * (z1-z2).conjugate()
    den = z1.conjugate() * z2
    den -= den.conjugate()
    return (num / den) + z0

A = []
for comb in itertools.combinations(Z,3):
    O = find_O(*comb)
    if O is None:
        continue
    A.append(O)
    
for z1,z2 in itertools.combinations(Z,2):
    O = (z1 + z2) / 2
    A.append(O)

Z = np.array(Z); A = np.array(A)

answer = np.abs((Z[:,None] - A[None,:])).max(axis = 0).min()
print(answer)

Submission Info

Judge Result