#944114 (Python3) No.2602 Real Collider

提出ソース

結果

問題	No.2602 Real Collider
ユーザー	FromBooska
提出日時	2024-01-13 22:03:32
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	WA
実行時間	-
コード長	4,773 bytes
コンパイル時間	398 ms
コンパイル使用メモリ	12,416 KB
実行使用メモリ	80,244 KB
最終ジャッジ日時	2024-01-13 22:04:55
合計ジャッジ時間	75,763 ms
ジャッジサーバーID （参考情報）	judge15 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	470 ms 43,904 KB
testcase_01	AC	446 ms 43,888 KB
testcase_02	AC	440 ms 43,892 KB
testcase_03	AC	451 ms 43,892 KB
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	AC	438 ms 43,888 KB
testcase_10	AC	1,710 ms 43,904 KB
testcase_11	WA	-
testcase_12	AC	1,037 ms 43,904 KB
testcase_13	AC	714 ms 43,892 KB
testcase_14	AC	1,080 ms 43,888 KB
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	AC	870 ms 43,892 KB
testcase_19	AC	950 ms 43,888 KB
testcase_20	WA	-
testcase_21	AC	810 ms 43,892 KB
testcase_22	AC	925 ms 43,892 KB
testcase_23	AC	796 ms 43,904 KB
testcase_24	AC	870 ms 43,904 KB
testcase_25	AC	933 ms 43,888 KB
testcase_26	WA	-
testcase_27	AC	993 ms 43,904 KB
testcase_28	WA	-
testcase_29	AC	925 ms 43,904 KB
testcase_30	AC	956 ms 43,904 KB
testcase_31	AC	989 ms 43,904 KB
testcase_32	AC	884 ms 43,892 KB
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	AC	1,029 ms 43,888 KB
testcase_38	AC	1,064 ms 43,888 KB
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	WA	-
testcase_43	AC	971 ms 43,888 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	681 ms 43,892 KB
testcase_53	AC	998 ms 43,892 KB
testcase_54	AC	845 ms 43,904 KB
testcase_55	WA	-
testcase_56	WA	-
testcase_57	WA	-
testcase_58	WA	-
testcase_59	AC	968 ms 43,888 KB
testcase_60	AC	902 ms 43,904 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	989 ms 43,892 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	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

# 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')

yukicoder

結果

テストケース

ソースコード