結果

問題 No.180 美しいWhitespace (2)
ユーザー rpy3cpprpy3cpp
提出日時 2015-05-19 18:05:22
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 3,611 bytes
コンパイル時間 75 ms
コンパイル使用メモリ 11,260 KB
実行使用メモリ 8,696 KB
最終ジャッジ日時 2023-09-20 10:13:41
合計ジャッジ時間 2,095 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 16 ms
8,564 KB
testcase_01 AC 17 ms
8,436 KB
testcase_02 AC 16 ms
8,556 KB
testcase_03 AC 17 ms
8,632 KB
testcase_04 AC 16 ms
8,552 KB
testcase_05 AC 17 ms
8,516 KB
testcase_06 WA -
testcase_07 AC 18 ms
8,552 KB
testcase_08 AC 19 ms
8,620 KB
testcase_09 AC 21 ms
8,552 KB
testcase_10 AC 21 ms
8,696 KB
testcase_11 AC 20 ms
8,616 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 21 ms
8,484 KB
testcase_16 AC 21 ms
8,612 KB
testcase_17 WA -
testcase_18 AC 21 ms
8,628 KB
testcase_19 AC 21 ms
8,496 KB
testcase_20 AC 17 ms
8,428 KB
testcase_21 AC 16 ms
8,132 KB
testcase_22 AC 17 ms
8,596 KB
testcase_23 AC 17 ms
8,472 KB
testcase_24 AC 16 ms
8,560 KB
testcase_25 AC 17 ms
8,196 KB
testcase_26 AC 16 ms
8,488 KB
testcase_27 AC 16 ms
8,252 KB
testcase_28 AC 16 ms
8,180 KB
testcase_29 AC 17 ms
8,544 KB
testcase_30 AC 20 ms
8,508 KB
testcase_31 AC 20 ms
8,548 KB
testcase_32 AC 19 ms
8,484 KB
testcase_33 AC 19 ms
8,676 KB
testcase_34 AC 19 ms
8,608 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
    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