Problem p03619 (python)

Fixed submission:
import operator
from bisect import bisect_left
from math import pi
import decimal


def lis(A):
    L = [A[0]]
    for a in A[1:]:
        if a > L[-1]:
            L.append(a)
        else:
            L[bisect_left(L, a)] = a
    return len(L)


def solve():
    x1, y1, x2, y2 = map(int, input().split())
    if x1 > x2:
        x1, y1, x2, y2 = x2, y2, x1, y1
    is_down = y1 > y2
    if is_down:
        y1, y2 = -y1, -y2
    base = decimal.Decimal(100) * (x2 - x1 + y2 - y1)

    n = int(input())
    fountains = []
    for _ in range(n):
        x, y = map(int, input().split())
        if is_down:
            y = -y
        if x < x1 or x2 < x or y < y1 or y2 < y:
            continue
        fountains.append((x, y))

    if not fountains:
        return str(base)

    dpi = decimal.Decimal(pi)

    fountains.sort()
    fountains_y = list(map(operator.itemgetter(1), fountains))
    mc = lis(fountains_y)
    if mc == min(x2 - x1, y2 - y1) + 1:
        dist = base + (dpi * 5 - 20) * (mc - 1) + dpi * 10 - 20
    else:
        dist = base + (dpi * 5 - 20) * mc
    return str(dist)


print(solve())

Buggy submission (verdict: Runtime Error):
import operator
from bisect import bisect_left
from math import pi
import decimal


def lis(A):
    L = [A[0]]
    for a in A[1:]:
        if a > L[-1]:
            L.append(a)
        else:
            L[bisect_left(L, a)] = a
    return len(L)


def solve():
    x1, y1, x2, y2 = map(int, input().split())
    if x1 > x2:
        x1, y1, x2, y2 = x2, y2, x1, y1
    is_down = y1 > y2
    if is_down:
        y1, y2 = -y1, -y2

    n = int(input())
    fountains = []
    for _ in range(n):
        x, y = map(int, input().split())
        if is_down:
            y = -y
        if x < x1 or x2 < x or y < y1 or y2 < y:
            continue
        fountains.append((x, y))
    fountains.sort()

    if x1 == x2:
        base = (y2 - y1) * 100
        for x, y in fountains:
            if x == x1:
                if y1 < y < y2:
                    return base + 10 * pi - 20
                else:
                    break
        return base
    if y1 == y2:
        base = (x2 - x1) * 100
        for x, y in fountains:
            if y == y1:
                if x1 < x < x2:
                    return base + 10 * pi - 20
                else:
                    break
        return base

    fountains_y = list(map(operator.itemgetter(1), fountains))
    mc = lis(fountains_y)
    dpi = decimal.Decimal(pi)
    base = decimal.Decimal((x2 - x1 + y2 - y1) * 100 - mc * 20)

    return str(base + mc * 5 * dpi)


print(solve())

Buggy submission (verdict: Runtime Error):
from math import pi


def solve():
    x1, y1, x2, y2 = map(int, input().split())
    if x1 > x2:
        x1, y1, x2, y2 = x2, y2, x1, y1
    is_down = y1 > y2
    if is_down:
        y1, y2 = -y1, -y2

    n = int(input())
    fountains = []
    for _ in range(n):
        x, y = map(int, input().split())
        if is_down:
            y = -y
        if x < x1 or x2 < x or y < y1 or y2 < y:
            continue
        fountains.append((y, x))
    fountains.sort()

    if x1 == x2:
        base = (y2 - y1) * 100
        for y, x in fountains:
            if x == x1:
                if y1 < y < y2:
                    return base + 10 * pi - 20
                else:
                    break
        return base
    if y1 == y2:
        base = (x2 - x1) * 100
        for y, x in fountains:
            if y == y1:
                if x1 < x < x2:
                    return base + 10 * pi - 20
                else:
                    break
        return base

    uncmp_x = sorted({x1, x2}.union(f[1] for f in fountains))
    uncmp_y = sorted({y1, y2}.union(f[0] for f in fountains))
    cmp_x = {x: i for i, x in enumerate(uncmp_x)}
    cmp_y = {y: i for i, y in enumerate(uncmp_y)}
    fountains = [(cmp_y[y], cmp_x[x]) for y, x in fountains]

    dp = [0] * len(uncmp_x)
    for y, x in fountains:
        cdp = dp.copy()
        for cx, cnt in enumerate(dp[:x]):
            cdp[cx] = max(dp[cx], cnt + 1)
        cdp[cx] = max(dp[cx], 1)
        dp = cdp

    mc = max(dp)
    return (x2 - x1 + y2 - y1) * 100 - mc * 20 + mc * 5 * pi


print(solve())

Buggy submission (verdict: Runtime Error):
from math import pi


def solve():
    x1, y1, x2, y2 = map(int, input().split())
    if x1 > x2:
        x1, y1, x2, y2 = x2, y2, x1, y1
    is_down = y1 > y2
    if is_down:
        y1, y2 = -y1, -y2

    n = int(input())
    fountains = []
    for _ in range(n):
        x, y = map(int, input().split())
        if is_down:
            y = -y
        if x < x1 or x2 < x or y < y1 or y2 < y:
            continue
        fountains.append((y, x))
    fountains.sort()

    if x1 == x2:
        base = (y2 - y1) * 100
        for y, x in fountains:
            if x == x1:
                if y1 < y < y2:
                    return base + 10 * pi - 20
                else:
                    break
        return base
    if y1 == y2:
        base = (x2 - x1) * 100
        for y, x in fountains:
            if y == y1:
                if x1 < x < x2:
                    return base + 10 * pi - 20
                else:
                    break
        return base

    uncmp_x = sorted({x1, x2, *(f[1] for f in fountains)})
    uncmp_y = sorted({y1, y2, *(f[0] for f in fountains)})
    cmp_x = {x: i for i, x in enumerate(uncmp_x)}
    cmp_y = {y: i for i, y in enumerate(uncmp_y)}
    fountains = [(cmp_y[y], cmp_x[x]) for y, x in fountains]

    dp = [0] * len(uncmp_x)
    for y, x in fountains:
        cdp = dp.copy()
        for cx, cnt in enumerate(dp[:x]):
            cdp[cx] = max(dp[cx], cnt + 1)
        cdp[cx] = max(dp[cx], 1)
        dp = cdp

    mc = max(dp)
    return (x2 - x1 + y2 - y1) * 100 - mc * 20 + mc * 5 * pi


print(solve())