結果

問題 No.180 美しいWhitespace (2)
ユーザー rpy3cpp
提出日時 2015-05-19 18:00:31
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 3,518 bytes
コンパイル時間 86 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-07-06 05:43:47
合計ジャッジ時間 2,168 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 24 WA * 5 RE * 2
権限があれば一括ダウンロードができます

ソースコード

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):
    # 凸包を得る
    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
    min_cost = float('inf')
    while min_idx >= 0 and max_idx >= 0:
        new_cost = min(min_cost, cost(ps, min_idx, max_idx, tab))
        if new_cost < min_cost:
            min_cost = new_cost
            best_tab = tab
        min_idx, max_idx, tab = get_next(ps, n, min_idx, max_idx, tab)
    xy = [x + tab * y for x, y in ps]
    if max(xy) - min(xy) < min_cost:
        best_tab = tab
    return best_tab


def cost(ps, min_idx, max_idx, tab):
    x1, y1 = ps[min_idx]
    x2, y2 = ps[max_idx]
    return x2 - x1 + (y2 - y1) * tab


def get_next(ps, n, min_idx, max_idx, tab):
    new_tab_f = tab
    while new_tab_f < tab + 1:
        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 and tab_max_f <= 0:
            return -1, -1, tab + 1
        if tab_min_f <= 0 or 0 < tab_max_f < tab_min_f:
            new_tab_f = tab_max_f
            max_idx = (max_idx + 1) % n
        elif tab_max_f <= 0 or 0 < tab_min_f < tab_max_f:
            new_tab_f = tab_min_f
            min_idx = (min_idx + 1) % n
        else:  # tab_min_f == tab_max_f:
            new_tab_f = tab_min_f
            min_idx = (min_idx + 1) % n
            max_idx = (max_idx + 1) % n
    new_tab = int(new_tab_f) + (1 if new_tab_f % 1 else 0)
    return min_idx, max_idx, new_tab


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

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