ARC051 A - 塗り絵

備忘録

問題

atcoder.jp

回答

import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def calcTwoPointDistance(x1, y1, x2, y2):
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    x1, y1, R = il()
    x2, y2, x3, y3 = il()
    RED = 'YES'
    BLUE = 'YES'

    if y2 <= y1 - R and y1 + R <= y3 and x2 <= x1 - R and x1 + R <= x3:
        RED = 'NO'

    dist = []
    for x in [x2, x3]:
        for y in [y2, y3]:
            dist.append(calcTwoPointDistance(x, y, x1, y1))
    if max(dist) <= R:
        BLUE = 'NO'

    print(RED)
    print(BLUE)


if __name__ == '__main__':
    main()

考え方

赤い円と青い四角がそれぞれ
独立した面積を持っているか否かを判定する。

赤い円は、中心点から上下左右にR進んだ位置の点が、
青い四角の1辺より内側に存在している場合には独立した面積を持たない。
そのため、上下(y1 + R, y1 - R)がy2y3の範囲内に収まっており、かつ、
左右(x1 - R, x1 + R)がx2x3の範囲内に収まっている場合には赤い円は独立した面積を持たない。

青い四角は、四角の各4点が赤い円の外側にあるか否かを判定する。
赤い円の周の座標は、全て赤い円の中心点から半径(R)だけ離れている。
そのため、青い四角が独立した面積を持つためには、
各4点と円の中心点との距離が半径(R)以上離れている必要がある。

四角の4点と円の中心点との距離が、1つでも半径(R)より長い場合には、
青い四角は独立した面積を持つことが出来る。