Submission #9461036


Source Code Expand

Copy
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

Submission Time
Task F - Enclose All
User maspy
Language Python (3.4.3)
Score 600
Code Size 907 Byte
Status AC
Exec Time 202 ms
Memory 37612 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 19
Set Name Test Cases
Sample 01.txt, 02.txt, 03.txt
All 01.txt, 02.txt, 03.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt
Case Name Status Exec Time Memory
01.txt AC 148 ms 12464 KB
02.txt AC 147 ms 12420 KB
03.txt AC 148 ms 12420 KB
10.txt AC 200 ms 37612 KB
11.txt AC 191 ms 35180 KB
12.txt AC 192 ms 35736 KB
13.txt AC 153 ms 13172 KB
14.txt AC 149 ms 12420 KB
15.txt AC 171 ms 21620 KB
16.txt AC 194 ms 33176 KB
17.txt AC 164 ms 18036 KB
18.txt AC 199 ms 37528 KB
19.txt AC 200 ms 37484 KB
20.txt AC 185 ms 30872 KB
21.txt AC 194 ms 33688 KB
22.txt AC 164 ms 17952 KB
23.txt AC 202 ms 37612 KB
24.txt AC 200 ms 37528 KB
25.txt AC 194 ms 33772 KB