Submission #2203192

---

Source Code Expand

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class Seg():
    def __init__(self, na, default, func):
        if isinstance(na, list):
            n = len(na)
        else:
            n = na
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        if isinstance(na, list):
            self.A = [default] * (self.N) + na + [default] * (self.N-n)
            for i in range(self.N-1,0,-1):
                self.A[i] = func(self.A[i*2], self.A[i*2+1])
        else:
            self.A = [default] * (self.N*2)
        self.F = func

    def find(self, i):
        return self.A[i + self.N]

    def update(self, i, x):
        i += self.N
        self.A[i] = x
        while i > 1:
            i = i // 2
            self.A[i] = self.merge(self.A[i*2], self.A[i*2+1])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[1]

    def query(self, a, b):
        A = self.A
        l = a + self.N
        r = b + self.N
        res = self.D
        while l < r:
            if l % 2 == 1:
                res = self.merge(res, A[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = self.merge(res, A[r])
            l >>= 1
            r >>= 1

        return res

def main():
    txy = LI()
    x1,y1,x2,y2 = txy
    n = I()
    a = [LI() for _ in range(n)]
    im = 10**8
    xs = set([x1,x2])
    ys = set([y1,y2])
    for x,y in a:
        xs.add(x)
        ys.add(y)
    xd = {}
    yd = {}
    i = 0
    for x in sorted(list(xs)):
        xd[x] = i
        i += 1
    i = 0
    for y in sorted(list(ys)):
        yd[y] = i
        i += 1
    x1 = xd[x1]
    x2 = xd[x2]
    y1 = yd[y1]
    y2 = yd[y2]
    a = [[xd[x],yd[y]] for x,y in a]

    if x1 > x2:
        x2,y2,x1,y1 = x1,y1,x2,y2
    if y1 > y2:
        y1 = im - y1
        y2 = im - y2 - y1
        for i in range(n):
            a[i][1] = im - a[i][1] - y1
    else:
        y2 -= y1
        for i in range(n):
            a[i][1] -= y1
    y1 = 0

    x2 -= x1
    for i in range(n):
        a[i][0] -= x1
    x1 = 0

    def f(a,b):
        if a > b:
            return a
        return b

    seg = Seg(y2,0,f)

    for x,y in sorted(a):
        if x < 0 or y < 0 or y > y2:
            continue
        t = seg.query(0,y+1)
        if seg.find(y) > t:
            continue
        seg.update(y, t+1)

    t = seg.total()
    kx = abs(txy[0]-txy[2])
    ky = abs(txy[1]-txy[3])
    r = (kx+ky) * 100
    if t == min(kx, ky) + 1:
        return r - t * 20 + math.pi * 5 * (t-1)  + math.pi * 10

    return r - t * 20 + math.pi * 5 * t


print(main())

Submission Info

Judge Result