문제 링크
문제 요약
n개의 콘센트 구멍이 주어집니다. 단, 모든 구멍은 서로 다른 위치에 있습니다.
각 구멍은 2차원 좌표 (x, y)와 함께 ‘노출’(0) 또는 ‘접지’(1) 중 하나의 타입을 가집니다.
두 접점 사이의 거리가 d인 플러그를 이 콘센트에 꽂을 수 있는지 여부를 확인하면서 한 접점은 ‘노출’ 구멍에, 다른 한 접점은 ‘접지’ 구멍에 연결될 수 있는지 확인해야 합니다.
풀이
플러그를 올바르게 연결하기 위해서는 두 가지 조건을 만족하는 두 개의 콘센트 구멍을 찾아야 합니다.
- 타입 일치: 플러그의 한 접점은 ‘노출’ 구멍(타입 0)에, 다른 한 접점은 ‘접지’ 구멍(타입 1)에 연결되어야 합니다. 즉, 선택된 두 구멍의 타입이 서로 달라야 합니다.
- 거리 일치: 선택된 두 구멍 사이의 유클리드 거리가 플러그의 접점 간 거리
d와 정확히 일치해야 합니다.
이 두 가지 조건을 동시에 만족하는 두 구멍 쌍이 존재하는지 확인하면 됩니다.
알고리즘 흐름:
- 모든 가능한 두 구멍 쌍을 반복하여 검사합니다.
N개의 구멍이 주어졌으므로,i번째 구멍과j번째 구멍(단,i < j)을 선택하는 모든 조합을 확인합니다. - 각 쌍
(hole_i, hole_j)에 대해 다음을 확인합니다:- 타입 확인:
hole_i의 타입과hole_j의 타입이 다른지 확인합니다. (holes[i][2] != holes[j][2])- 만약 두 구멍의 타입이 같다면, 이 쌍은 플러그 연결 조건에 맞지 않으므로 다음 쌍으로 넘어갑니다.
- 거리 확인: 두 구멍의 타입이 다르다면, 두 구멍
(x_i, y_i)와(x_j, y_j)사이의 유클리드 거리를 계산합니다.- 유클리드 거리 공식은
sqrt((x_i - x_j)^2 + (y_i - y_j)^2)입니다. - 부동 소수점 오차를 피하고 계산을 단순화하기 위해, 실제 거리를 계산하는 대신 거리의 제곱을 비교합니다. 즉,
(x_i - x_j)^2 + (y_i - y_j)^2가d^2와 같은지 확인합니다.
- 유클리드 거리 공식은
- 타입 확인:
- 만약 위 두 가지 조건을 모두 만족하는 구멍 쌍을 찾았다면, 플러그를 올바르게 연결할 수 있으므로 즉시 “Yes”를 출력하고 프로그램을 종료합니다.
- 모든 가능한 쌍을 검사했지만 조건을 만족하는 쌍을 하나도 찾지 못했다면, “No”를 출력합니다.
시간 복잡도:
구멍의 개수 N에 대해, 모든 가능한 두 구멍 쌍을 검사하므로 시간 복잡도는 O(N^2)입니다. 문제에서 N의 최대값이 200이므로, 200^2 = 40,000번의 연산은 충분히 허용 가능한 범위 내에 있습니다.
공간 복잡도: 구멍들의 좌표와 타입을 저장하는 데 O(N)의 공간이 필요합니다.
정답 코드
"""
[22177: Универсальная розетка](https://www.acmicpc.net/problem/22177)
Tier: Bronze 1
Category: geometry, implementation, math, pythagoras
"""
import sys
from math import sqrt, pi, sin, factorial, ceil, floor
from datetime import datetime, timedelta
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, product
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop, heapify
from functools import reduce, lru_cache
from operator import itemgetter, attrgetter, mul, add, sub, truediv
from typing import List, Tuple, Dict, Set, Any, Union
SYS_INPUT = True
RECURSION_LIMIT = 10 ** 7
SET_RECURSION = False
BLANK = " "
if SET_RECURSION:
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda : sys.stdin.readline().rstrip() if SYS_INPUT else input()
mii = lambda : [*map(int,inp().split())]
mfi = lambda : [*map(float,inp().split())]
ii = lambda : int(inp())
fi = lambda : float(inp())
isplit = lambda : inp().split()
p = print
def gcd(a, b): return gcd(b, a % b) if b > 0 else a
def lcm(a, b): return a * b // gcd(a, b)
def solve():
n, d = mii()
holes = [mii() for _ in range(n)]
for i in range(n):
for j in range(i + 1, n): # 중복 검사를 피하기 위해 j는 i + 1부터 시작
if holes[i][2] == holes[j][2]: # 두 구멍의 타입이 같으면 (둘 다 0이거나 둘 다 1)
continue # 다음 쌍으로 넘어감
# 두 구멍의 타입이 다를 경우 (하나 0, 하나 1)
# 두 구멍 사이의 거리의 제곱을 계산하여 d의 제곱과 비교
if d * d != (holes[i][0] - holes[j][0]) ** 2 + (holes[i][1] - holes[j][1]) ** 2:
continue # 거리가 d가 아니면 다음 쌍으로 넘어감
# 타입도 다르고, 거리도 d인 쌍을 찾았으므로 "Yes" 반환
return "Yes"
# 모든 쌍을 검사했지만 조건을 만족하는 쌍을 찾지 못함
return "No"
if __name__ == "__main__":
tc = 1
for t in range(1, tc+1):
ret = solve()
print(ret)