結果

問題 No.180 美しいWhitespace (2)
ユーザー rpy3cpprpy3cpp
提出日時 2015-05-19 18:41:52
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 3,919 bytes
コンパイル時間 73 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 11,264 KB
最終ジャッジ日時 2024-07-06 05:44:04
合計ジャッジ時間 1,915 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
11,008 KB
testcase_01 AC 29 ms
11,136 KB
testcase_02 AC 27 ms
11,136 KB
testcase_03 WA -
testcase_04 AC 27 ms
11,136 KB
testcase_05 AC 28 ms
11,136 KB
testcase_06 AC 28 ms
11,136 KB
testcase_07 AC 30 ms
11,136 KB
testcase_08 AC 30 ms
11,136 KB
testcase_09 AC 31 ms
11,136 KB
testcase_10 AC 33 ms
11,136 KB
testcase_11 AC 33 ms
11,136 KB
testcase_12 AC 30 ms
11,264 KB
testcase_13 AC 31 ms
11,136 KB
testcase_14 AC 32 ms
11,136 KB
testcase_15 AC 30 ms
11,136 KB
testcase_16 AC 34 ms
11,136 KB
testcase_17 AC 31 ms
11,136 KB
testcase_18 AC 31 ms
11,136 KB
testcase_19 AC 32 ms
11,136 KB
testcase_20 AC 26 ms
11,264 KB
testcase_21 AC 26 ms
11,136 KB
testcase_22 AC 25 ms
11,008 KB
testcase_23 AC 25 ms
11,136 KB
testcase_24 AC 26 ms
11,136 KB
testcase_25 AC 26 ms
11,136 KB
testcase_26 AC 26 ms
11,136 KB
testcase_27 AC 25 ms
11,008 KB
testcase_28 AC 26 ms
11,008 KB
testcase_29 AC 26 ms
11,136 KB
testcase_30 AC 31 ms
11,136 KB
testcase_31 AC 32 ms
11,136 KB
testcase_32 AC 29 ms
11,136 KB
testcase_33 AC 30 ms
11,136 KB
testcase_34 AC 28 ms
11,264 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def convex_hull(points):
    '''二次元平面上の点のリスト points の凸包を返す。Andrew のアルゴリズムを使用。
    引数：
        points = [(x0, y0), (x1, y1),...] 点のリスト
        同じ点は含まない（全て異なる点である）とする。
    返り値:
        convex_hull = [(xi, yi), (xj, yj),...] 点のリスト。時計回りに並んでいる。
    '''
    points.sort()
    upper_bounds = get_bounds(points)
    points.reverse()
    lower_bounds = get_bounds(points)
    del upper_bounds[-1]
    del lower_bounds[-1]
    upper_bounds.extend(lower_bounds)
    return upper_bounds


def get_bounds(points):
    bounds = [points[0], points[1]]
    for xi, yi in points[2:]:
        while len(bounds) > 1 and not is_convex(bounds, xi, yi):
            del bounds[-1]
        bounds.append((xi, yi))
    return bounds


def is_convex(bounds, x2, y2):
    x1, y1 = bounds[-1]
    x0, y0 = bounds[-2]
    return (x1 - x0) * (y2 - y1) < (y1 - y0) * (x2 - x1)


def read_data():
    N = int(input())
    AB = [tuple(map(int, input().split())) for i in range(N)]
    return N, AB


def solve(N, AB):
    # 重複する点を除く
    AB = list(set(AB))
    if len(AB) == 1:
        return 1

    # 凸包を得る
    ps = convex_hull(AB)
    ps.reverse()         # 反時計回りに並べ直す。

    # tab = 1 としたときの最小値と最大値の出現場所にカーソルをおく。
    xy = [x + y for x, y in ps]
    min_xy = min(xy)
    max_xy = max(xy)
    min_idx = xy.index(min_xy)
    max_idx = xy.index(max_xy)

    # 凸包を半時計回りに走査して、 x + tab * y の幅が最小となる tab をさがす。
    return find_best_tab_width(ps, min_idx, max_idx)


def find_best_tab_width(ps, min_idx, max_idx):
    n = len(ps)
    tab = 1.0
    min_cost = float('inf')
    while tab > 0:
        tab_int0 = int(tab)
        tab_int1 = tab_int0 + 1
        new_cost0 = cost(ps, min_idx, max_idx, tab_int0, n)
        new_cost1 = cost(ps, min_idx, max_idx, tab_int1, n)
        if new_cost0 < min_cost:
            min_cost = new_cost0
            best_tab = tab_int0
        if new_cost1 < min_cost:
            min_cost = new_cost1
            best_tab = tab_int1
        min_idx, max_idx, tab = get_next(ps, n, min_idx, max_idx, tab)
    return best_tab


def cost(ps, min_idx, max_idx, tab, n):
    '''計算誤差に対処するため、最小値, 最大値をとるはずのidx の前後についても計算している。
    '''
    min_idxs = [(min_idx-1) % n, min_idx, (min_idx+1) % n]
    min_val = min([ps[i][0] + tab * ps[i][1] for i in min_idxs])
    max_idxs = [(max_idx-1) % n, max_idx, (max_idx+1) % n]
    max_val = max([ps[i][0] + tab * ps[i][1] for i in max_idxs])
    return max_val - min_val


def get_next(ps, n, min_idx, max_idx, tab):
    min_x0, min_y0 = ps[min_idx]
    min_x1, min_y1 = ps[(min_idx + 1) % n]
    max_x0, max_y0 = ps[max_idx]
    max_x1, max_y1 = ps[(max_idx + 1) % n]
    dx_min, dy_min = min_x1 - min_x0, min_y0 - min_y1
    dx_max, dy_max = max_x0 - max_x1, max_y1 - max_y0
    tab_min_f = get_slope(dx_min, dy_min)
    tab_max_f = get_slope(dx_max, dy_max)
    if tab_min_f == 0:
        return min_idx, (max_idx + 1) % n, tab_max_f
    if tab_max_f == 0:
        return (min_idx + 1) % n, max_idx, tab_min_f
    if tab_min_f < tab_max_f:
        return (min_idx + 1) % n, max_idx, tab_min_f
    if tab_max_f < tab_min_f:
        return min_idx, (max_idx + 1) % n, tab_max_f
    else:
        return (min_idx + 1) % n, (max_idx + 1) % n, tab_min_f


def get_slope(dx, dy):
    if dx <= 0 or dy <= 0:
        return 0
    else:
        return 1.0 * dx / dy


def checker(tab, AB):
    for TAB in [tab - 1, tab, tab + 1]:
        xy = [x + TAB * y for x, y in AB]
        score = max(xy) - min(xy)
        print(score)

if __name__ == '__main__':
    N, AB = read_data()
    print(solve(N, AB))
0