QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#263727#5104. Guardians of the Galleryjorgedg611RE 0ms0kbPython37.2kb2023-11-25 04:51:462023-11-25 04:51:46

Judging History

你现在查看的是最新测评结果

  • [2023-11-25 04:51:46]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-11-25 04:51:46]
  • 提交

answer

import math
from queue import PriorityQueue

EPS = 1e-11
DINF = 1e9


class pt:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, p):
        return abs(self.x - p.x) <= EPS and abs(self.y - p.y) <= EPS

    def __add__(self, p):
        return pt(self.x + p.x, self.y + p.y)

    def __sub__(self, p):
        return pt(self.x - p.x, self.y - p.y)

    def __mul__(self, t):
        return pt(self.x * t, self.y * t)

    def __truediv__(self, t):
        return pt(self.x / t, self.y / t)

    def __matmul__(self, p):
        return self.x * p.x + self.y * p.y

    def norm2(self):
        return self @ self

    def norm(self):
        return math.sqrt(float(self.norm2()))

    def unit(self):
        return self / self.norm()

    def __mod__(self, p):
        return self.x * p.y - self.y * p.x

    def __lt__(self, p):
        return self.x < p.x - EPS or (abs(self.x - p.x) <= EPS and self.y < p.y - EPS)

    def left(self, p, q):
        return (q - p) % (self - p) > EPS

    def right(self, p, q):
        return (q - p) % (self - p) < -EPS

    def in_seg(self, p, q):
        return abs((q - p) % (self - p)) < EPS

    def rot(self, r):
        return pt(self % r, self * r)


def ccw90():
    return pt(1, 0)


def cw90():
    return pt(-1, 0)


def sgn(x):
    return -1 if x < -EPS else 1 if x > EPS else 0


class Cmp:
    def __init__(self, r):
        self.r = r

    def cuad(self, a):
        if a.x > EPS and a.y >= -EPS:
            return 0
        if a.x <= EPS and a.y > EPS:
            return 1
        if a.x < -EPS and a.y <= EPS:
            return 2
        if a.x >= -EPS and a.y < -EPS:
            return 3
        return -1

    def cmp(self, p1, p2):
        c1 = self.cuad(p1)
        c2 = self.cuad(p2)
        me = p1.y * p2.x
        he = p1.x * p2.y
        pp1 = p1
        pp2 = p2
        if c1 == c2:
            return me + EPS < he or (abs(me - he) < EPS and pp1.norm() + EPS < pp2.norm())
        return c1 < c2

    def __call__(self, p1, p2):
        return self.cmp(p1 - self.r, p2 - self.r)


class ln:
    def __init__(self, p, q):
        self.p = p
        self.pq = q - p

    def __truediv__(self, l):
        return abs(self.pq.unit() % l.pq.unit()) <= EPS

    def __xor__(self, l):
        if self / l:
            return pt(DINF, DINF)
        r = l.p + l.pq * ((self.p - l.p) % self.pq / (l.pq % self.pq))
        return r

    def proj(self, r):
        return self.p + self.pq * ((r - self.p) @ self.pq / self.pq.norm2())


def seghas(a, b, c):
    me = (a - b).norm()
    he = (a - c).norm() + (b - c).norm()
    return abs(me - he) < EPS


def has(p, q):
    n = len(p)
    for i in range(n):
        if seghas(p[i], p[(i + 1) % n], q):
            return True
    cnt = 0
    for i in range(n):
        j = (i + 1) % n
        k = sgn((q - p[j]) % (p[i] - p[j]))
        u = sgn(p[i].y - q.y)
        v = sgn(p[j].y - q.y)
        if k > 0 and u < 0 and v >= 0:
            cnt += 1
        if k < 0 and v < 0 and u >= 0:
            cnt -= 1
    return cnt != 0


def between(a, b, c):
    o = pt(0, 0)
    if b.left(o, a):
        return not c.left(o, a) or not c.right(o, b)
    else:
        return not c.right(o, b) and not c.left(o, a)


def getdist(p, dir, v):
    n = len(v)
    for i in range(n):
        if v[i] == p:
            pre = v[(i - 1 + n) % n]
            nex = v[(i + 1) % n]
            if not between(pre - p, nex - p, dir):
                return 0

    lef = 1e18
    rig = 1e18
    asd = p + dir.rot(cw90())

    for i in range(n):
        a = v[i]
        b = v[(i + 1) % n]

        if abs(dir % (b - a)) < EPS:
            if p.in_seg(a, b):
                if a == p:
                    rig = 0
                if b == p:
                    lef = 0
                if a.left(p, asd) and b.left(p, asd):
                    if (a - p).norm() < (b - p).norm():
                        rig = min(rig, (a - p).norm())
                    else:
                        lef = min(lef, (b - p).norm())
        else:
            to = ln(a, b) ^ ln(p, p + dir)
            asd = p + dir.rot(cw90())
            if not seghas(a, b, to) or to.right(p, asd):
                continue

            ds = (to - p).norm()

            if to == p:
                continue

            if to == a:
                if b.right(p, p + dir):
                    rig = min(rig, ds)
                else:
                    lef = min(lef, ds)
            elif to == b:
                if a.right(p, p + dir):
                    rig = min(rig, ds)
                else:
                    lef = min(lef, ds)
            else:
                lef = min(lef, ds)
                rig = min(rig, ds)

    ans = max(lef, rig)
    return ans


def getbox(p, v):
    vv = sorted(v, key=Cmp(p))

    ans = []
    for i in range(len(vv)):
        if i and vv[i].in_seg(vv[i - 1], p):
            continue

        q = vv[i]
        dir = (q - p).unit()

        now = getdist(p, dir, v)
        me = p + (dir * now)

        he = (vv[i] - p).norm()
        if he <= now + EPS:
            pos = -1
            n = len(v)
            for j in range(n):
                if v[j] == vv[i]:
                    pos = (j - 1 + n) % n
            if not v[pos].left(p, vv[i]):
                me, q = q, me
            ans.append(me)
            ans.append(q)
        else:
            ans.append(me)

    ans = list(set(ans))
    return ans


def getdir(a, b, c):
    pr = ln(a, b).proj(c)
    if seghas(a, b, pr):
        return pr
    elif (a - c).norm() < (b - c).norm():
        return a
    return b


MAXN = 110
g = [[] for _ in range(MAXN)]
bst = [1e18] * MAXN

n = int(input())
v = [pt(0, 0) for _ in range(n + 2)]
for i in range(n + 2):
    x, y = map(int, input().split())
    v[i] = pt(x, y)

me = v[n]
he = v[n + 1]
v = v[:-2]

for i in range(n):
    for j in range(n):
        if i != j:
            mx = getdist(v[i], (v[j] - v[i]).unit(), v)
            he = (v[j] - v[i]).norm()
            if he <= mx + EPS:
                g[i].append((j, he))

for i in range(n):
    mx = getdist(me, (v[i] - me).unit(), v)
    he = (me - v[i]).norm()
    if he <= mx + EPS:
        g[n].append((i, he))

box = getbox(he, v)
vv = v + [me]

for i in range(n + 1):
    bst[i] = 1e18

    if has(box, vv[i]):
        bst[i] = 0
        continue

    for j in range(len(box)):
        p = box[j]
        q = box[(j + 1) % len(box)]
        to = getdir(p, q, vv[i])
        mx = getdist(vv[i], (to - vv[i]).unit(), v)
        he = (to - vv[i]).norm()
        if he <= mx + EPS:
            bst[i] = min(bst[i], he)

for i in range(n + 1):
    g[i].append((n + 1, bst[i]))

q = PriorityQueue()
ans = [1e18] * (n + 2)
q.put((0, n))
ans[n] = 0

while not q.empty():
    d, pos = q.get()
    if abs(ans[pos] - d) > EPS:
        continue
    for x in g[pos]:
        nd = d + x[1]
        if nd + EPS < ans[x[0]]:
            ans[x[0]] = nd
            q.put((nd, x[0]))

res = 1e18
print("{:.10f}".format(float(ans[n + 1])))

详细

Test #1:

score: 0
Dangerous Syscalls

input:

15
13 7
20 20
39 20
49 7
73 13
100 5
117 38
98 20
80 20
66 40
68 20
51 20
41 39
22 48
2 39
10 20
104 20

output:


result: