square869120Contest #1 B - ケーキ・カッティング (Cake Cutting)

問題

B: ケーキ・カッティング (Cake Cutting) - square869120Contest #1 | AtCoder

H×Wの大きさのケーキを2人で分ける。ケーキは長方形であり, 4頂点の座標は(0,0),(0,H),(W,0),(W,H)である。

square1001は, 座標(0,0)から(i,H)(1≦i≦W)または(W,i)(1≦i≦H)に向かって切る。しかし, 次の条件を満たさなければならない。

• ケーキの上にはイチゴがN個あり, それを均等に分けなければならない。
• ナイフがイチゴの上にくるように切るとイチゴは消えてしまうので, イチゴを1個も消滅させないように切らなければならない。

そのとき, square1001が(0,0)からPに向かって切るようなPをすべて求めなさい。ただし, そのようなことができないときは−1と出力しなさい。

ただし、イチゴの面積は考えないものとします。

解法

まず、イチゴが奇数個の場合には2人で等分できないのではじく。

イチゴが偶数のとき、条件を判定するには符号付き面積Sを用いればよい。

• S = 0 → 境界線上にイチゴがあるので不可
• S > 0 と S < 0 の個数をカウントし、差が0なら等分できている

def area(x1, y1, x2, y2):
    return x1*y2 - y1*x2
 
def print_ans(x, y):
    x = str(x); y = str(y)
    print('(' + x + ',' + y + ')')
 
H, W, N = map(int, input().split())
berry = []
for i in range(N):
    berry.append(list(map(int, input().split())))
if N % 2 != 0:
    print(-1)
else:
    ans = []
    #(i, H) 1<=i<=W-1
    for i in range(1, W):
        cnt = 0
        for b in berry:
            S = area(b[0], b[1], i, H) 
            if S == 0:
                cnt = -1
                break
            if S > 0:
                cnt += 1
            else:
                cnt -= 1
        if cnt == 0:
            ans.append([i, H])
    
    #(W, i) 1<=i<=H
    for i in range(1, H+1):
        cnt = 0
        for b in berry:
            S = area(b[0], b[1], W, i) 
            if S == 0:
                cnt = -1
                break
            if S > 0:
                cnt += 1
            else:
                cnt -= 1
        if cnt == 0:
            ans.append([W, i])
    
    if ans == []:
        print(-1)
    else:
        ans.sort()
        for ax in ans:
            print_ans(ax[0], ax[1])

最近のABC埋めで培った知識を活かせたので満足。といっても本番はあくせくしながらなんとか通したって感じでしたけど。