結果

問題 No.2602 Real Collider
ユーザー FromBooskaFromBooska
提出日時 2024-01-13 22:03:32
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 4,773 bytes
コンパイル時間 462 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 45,136 KB
最終ジャッジ日時 2024-09-28 01:49:35
合計ジャッジ時間 78,515 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 454 ms
44,924 KB
testcase_01 AC 449 ms
44,680 KB
testcase_02 AC 452 ms
44,544 KB
testcase_03 AC 455 ms
44,548 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 449 ms
44,548 KB
testcase_10 AC 1,708 ms
44,284 KB
testcase_11 WA -
testcase_12 AC 1,052 ms
45,064 KB
testcase_13 AC 728 ms
44,544 KB
testcase_14 AC 1,071 ms
44,476 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 909 ms
44,300 KB
testcase_19 AC 970 ms
44,164 KB
testcase_20 WA -
testcase_21 AC 857 ms
45,064 KB
testcase_22 AC 936 ms
44,300 KB
testcase_23 AC 780 ms
44,680 KB
testcase_24 AC 920 ms
44,892 KB
testcase_25 AC 965 ms
44,544 KB
testcase_26 WA -
testcase_27 AC 1,023 ms
44,292 KB
testcase_28 WA -
testcase_29 AC 951 ms
44,544 KB
testcase_30 AC 1,005 ms
44,544 KB
testcase_31 AC 1,008 ms
44,264 KB
testcase_32 AC 933 ms
44,680 KB
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 AC 1,051 ms
44,548 KB
testcase_38 AC 1,070 ms
44,800 KB
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 AC 991 ms
44,292 KB
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 AC 705 ms
45,064 KB
testcase_53 AC 1,025 ms
44,812 KB
testcase_54 AC 876 ms
44,420 KB
testcase_55 WA -
testcase_56 WA -
testcase_57 WA -
testcase_58 WA -
testcase_59 AC 1,004 ms
44,300 KB
testcase_60 AC 937 ms
44,420 KB
testcase_61 WA -
testcase_62 WA -
testcase_63 WA -
testcase_64 WA -
testcase_65 WA -
testcase_66 WA -
testcase_67 WA -
testcase_68 WA -
testcase_69 WA -
testcase_70 WA -
testcase_71 WA -
testcase_72 AC 979 ms
44,676 KB
testcase_73 WA -
testcase_74 WA -
testcase_75 WA -
testcase_76 WA -
testcase_77 WA -
testcase_78 WA -
testcase_79 WA -
testcase_80 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

# https://rosettacode.org/wiki/Smallest_enclosing_circle_problem#Python

import numpy as np

class ProjectorStack:
    """
    Stack of points that are shifted / projected to put first one at origin.
    """
    def __init__(self, vec):
        self.vs = np.array(vec)
        
    def push(self, v):
        if len(self.vs) == 0:
            self.vs = np.array([v])
        else:
            self.vs = np.append(self.vs, [v], axis=0)
        return self
    
    def pop(self):
        if len(self.vs) > 0:
            ret, self.vs = self.vs[-1], self.vs[:-1]
            return ret
    
    def __mul__(self, v):
        s = np.zeros(len(v))
        for vi in self.vs:
            s = s + vi * np.dot(vi, v)
        return s
    
class GaertnerBoundary:
    """
        GärtnerBoundary

    See the passage regarding M_B in Section 4 of Gärtner's paper.
    """
    def __init__(self, pts):
        self.projector = ProjectorStack([])
        self.centers, self.square_radii = np.array([]), np.array([])
        self.empty_center = np.array([np.NaN for _ in pts[0]])


def push_if_stable(bound, pt):
    if len(bound.centers) == 0:
        bound.square_radii = np.append(bound.square_radii, 0.0)
        bound.centers = np.array([pt])
        return True
    q0, center = bound.centers[0], bound.centers[-1]
    C, r2  = center - q0, bound.square_radii[-1]
    Qm, M = pt - q0, bound.projector
    Qm_bar = M * Qm
    residue, e = Qm - Qm_bar, sqdist(Qm, C) - r2
    z, tol = 2 * sqnorm(residue), np.finfo(float).eps * max(r2, 1.0)
    isstable = np.abs(z) > tol
    if isstable:
        center_new  = center + (e / z) * residue
        r2new = r2 + (e * e) / (2 * z)
        bound.projector.push(residue / np.linalg.norm(residue))
        bound.centers = np.append(bound.centers, np.array([center_new]), axis=0)
        bound.square_radii = np.append(bound.square_radii, r2new)
    return isstable

def pop(bound):
    n = len(bound.centers)
    bound.centers = bound.centers[:-1]
    bound.square_radii = bound.square_radii[:-1]
    if n >= 2:
        bound.projector.pop()
    return bound


class NSphere:
    def __init__(self, c, sqr):
        self.center = np.array(c)
        self.sqradius = sqr

def isinside(pt, nsphere, atol=1e-6, rtol=0.0):
    r2, R2 = sqdist(pt, nsphere.center), nsphere.sqradius
    return r2 <= R2 or np.isclose(r2, R2, atol=atol**2,rtol=rtol**2)

def allinside(pts, nsphere, atol=1e-6, rtol=0.0):
    for p in pts:
        if not isinside(p, nsphere, atol, rtol):
            return False
    return True

def move_to_front(pts, i):
    pt = pts[i]
    for j in range(len(pts)):
        pts[j], pt = pt, np.array(pts[j])
        if j == i:
            break
    return pts

def dist(p1, p2):
    return np.linalg.norm(p1 - p2)

def sqdist(p1, p2):
    return sqnorm(p1 - p2)

def sqnorm(p):
    return np.sum(np.array([x * x for x in p]))

def ismaxlength(bound):
    len(bound.centers) == len(bound.empty_center) + 1

def makeNSphere(bound):
    if len(bound.centers) == 0: 
        return NSphere(bound.empty_center, 0.0)
    return NSphere(bound.centers[-1], bound.square_radii[-1])

def _welzl(pts, pos, bdry):
    support_count, nsphere = 0, makeNSphere(bdry)
    if ismaxlength(bdry):
        return nsphere, 0
    for i in range(pos):
        if not isinside(pts[i], nsphere):
            isstable = push_if_stable(bdry, pts[i])
            if isstable:
                nsphere, s = _welzl(pts, i, bdry)
                pop(bdry)
                move_to_front(pts, i)
                support_count = s + 1
    return nsphere, support_count

def find_max_excess(nsphere, pts, k1):
    err_max, k_max = -np.Inf, k1 - 1
    for (k, pt) in enumerate(pts[k_max:]):
        err = sqdist(pt, nsphere.center) - nsphere.sqradius
        if  err > err_max:
            err_max, k_max = err, k + k1
    return err_max, k_max - 1

def welzl(points, maxiterations=2000):
    pts, eps = np.array(points, copy=True), np.finfo(float).eps
    bdry, t = GaertnerBoundary(pts), 1
    nsphere, s = _welzl(pts, t, bdry)
    for i in range(maxiterations):
        e, k = find_max_excess(nsphere, pts, t + 1)
        if e <= eps:
            break
        pt = pts[k]
        push_if_stable(bdry, pt)
        nsphere_new, s_new = _welzl(pts, s, bdry)
        pop(bdry)
        move_to_front(pts, k)
        nsphere = nsphere_new
        t, s = s + 1, s_new + 1
    return nsphere

Q = int(input())
x1, y1, x2, y2, x3, y3 = map(int, input().split())
points = np.array([[x1, y1], [x2, y2], [x3, y3]])
nsphere = welzl(points)
cx = nsphere.center[0]
cy = nsphere.center[1]
r2 = nsphere.sqradius
#print(cx, cy, r2)

for i in range(Q):
    x, y = map(int, input().split())
    if (x-cx)**2+(y-cy)**2 <= r2:
        print('Yes')
    else:
        print('No')
0