水面下の夢

競プロやイラストに興味があります.メインブログがここ.同人サークル「かのらぶ」のページはこっち( https://yumechi0525.amebaownd.com ).ブログアイコンはYaQ(@8_9_00)さんから.

ARC051 A - 塗り絵

A: 塗り絵 - AtCoder Regular Contest 051 | AtCoder

本番未参加なので初見です。ただ、本番出ていたら多分これ解けなかったです。理由はグラフ上の図形とか含まれるとか非情に苦手なので。


やること自体としては非情に単純で、円が長方形に完全に含まれていなければ赤色はYES、逆ならNO。長方形が完全に円に含まれていなければ青色はYES、逆ならNOッて感じですね。


まず赤色について考えると、円の上下左右4点が長方形の中にあるかどうかで判定ができます。円の上下左右のうち、例えば上の点について考えると、円のx座標をx、y座標をy、半径をrとしたときに、(長方形の左側のx座標 <= x <= 長方形の右側のx座標) かつ (長方形の下側のy座標 <= (y + h) <= 長方形の上側のy座標)で判定ができます。上下左右ということなので、(x - h, y), (x + h, y), (x, y - h), (x, y + h) の4点について考えます。4点とも含まれているのであれば円は長方形の内部にあります。


次に青色について考えると長方形の頂点4点全てについて円の中にあるかどうかで判定ができます。円の中にあるかどうかは、(長方形の頂点と円の中心の距離) <= (円の半径)で判定ができます。これを長方形の頂点4点に適応し、4点とも含まれているのであれば長方形は円の内部にあります。


ということで、ライブラリ化することも見越しながら(ライブラリになるとは言っていない)メソッドを大量に作って問題を解いてみました。実はドキュメントありのものもあるのですが、冗長になるのでブログにはドキュメントなしの方を掲載させていただきます。ドキュメントありの回答については以下にリンクを用意しましたので、興味のある方は御覧ください。

ドキュメントなし

Submission #716002 - AtCoder Regular Contest 051 | AtCoder

def calcDistance(x1, y1, x2, y2):
    x = x1 - x2
    y = y1 - y2
    return pow(x ** 2 + y ** 2, 0.5)

def inCircle(cx, cy, r, x, y):
    return calcDistance(cx, cy, x, y) <= r

def inRectangle(rx1, ry1, rx2, ry2, x, y):
    if rx1 == rx2 or ry1 == ry2:
        # 未チェック
        import sys
        sys.stderr.write("長方形の座標値がおかしいです")
        print(" ".join(["rx1", "rx2", "ry1", "ry2"]))
        print(" ".join([str(i) for i in [rx1, rx2, ry1, ry2]]))
        raise Exception

    # 大きさチェック
    if rx2 < rx1:
        rx1, rx2 = rx2, rx1
    if ry2 < ry1:
        ry1, ry2 = ry2, ry1
    return rx1 <= x <= rx2 and ry1 <= y <= ry2

def circleInRectangle(cx, cy, r, rx1, ry1, rx2, ry2):
    l1 = [-1, 1, -1, 1]
    l2 = [1, 1, -1, -1]
    cnt = 0
    for i in range(4):
        if(inRectangle(rx1, ry1, rx2, ry2, (cx + r * l1[i]), (cy + r * l2[i]))):
            cnt += 1
    return cnt == 4

def rectangleInCircle(rx1, ry1, rx2, ry2, cx, cy, r):
    l1 = [rx1, rx2, rx1, rx2]
    l2 = [ry1, ry1, ry2, ry2]
    cnt = 0
    for i in range(4):
        if(inCircle(cx, cy, r, l1[i], l2[i])):
            cnt += 1
    return cnt == 4

def solve():
    cx, cy, r = map(int, input().split())
    rx1, ry1, rx2, ry2 = map(int, input().split())
    # RED:CIRCLE
    print("NO" if circleInRectangle(cx, cy, r, rx1, ry1, rx2, ry2) else "YES")
    # BLUE:RECTANGLE
    print("NO" if rectangleInCircle(rx1, ry1, rx2, ry2, cx, cy, r) else "YES")

if __name__=="__main__":
    solve()