QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#263727 | #5104. Guardians of the Gallery | jorgedg611 | RE | 0ms | 0kb | Python3 | 7.2kb | 2023-11-25 04:51:46 | 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