숨어있는 기준을 찾는 브루트포스1 - 수많은 좌표들을 얼마나 평행이동해야 일치하는가

5588번: 별자리 찾기

 

좌표 집합 A와 B가 주어질때 A를 얼마나 평행이동 시켜야 B의 부분집합이 될 수 있는가?

 

아래의 경우 2,-3 이동시키면 B의 빨간 부분과 일치시킬 수 있다

 

 

 

A의 별 개수 m이 최대 200개이고 B의 별 개수 n이 최대 1000개

 

x,y값은 최대 10^6까지...

 

그러면 200개 * 1000개 돌아보면서... 평행이동 시킬 수 있는 양 10^6까지 하나하나 돌아봐야하나??

 

그런데 A의 모든 점은 서로 동일하게 (dx,dy)만큼 이동한다는 점 + 

 

B의 점들 집합의 일부가 되어야하므로, A의 한 점이 B의 모든 점 각각에 대하여 얼마만큼 이동해야 가능한지

 

(dx,dy)를 모두 구해놓는다면?

 

 

 

 

가능한 (dx,dy) 후보는 최대 1000개이고 각각에 대해서 A의 모든 점에 대해 (dx,dy)만큼 이동시켜 본 다음

 

B에 속하는지 체크해본다면? O(1000*200)으로 가능함

 

from sys import stdin

m = int(stdin.readline())

A = []

for _ in range(m):
    
    x,y = map(int,stdin.readline().split())
    A.append((x,y))

n = int(stdin.readline())

B = {}

for i in range(n):
    
    x,y = map(int,stdin.readline().split())

    B[(x,y)] = i

delta = []

X = A[0][0]
Y = A[0][1]

for x,y in B:
    
    delta.append((x - X,y - Y))

for dx,dy in delta:
    
    visited = [0]*n
    
    no = False

    for i in range(m):
        
        x,y = A[i]

        if B.get((x + dx, y + dy),-1) == -1:
            
            no = True
            break
        
        else:
            
            v = B[(x+dx,y+dy)]

            if visited[v] == 1:
                
                no = True
                break
            
            else:
                
                visited[v] = 1
    
    if no == False:
        
        break

print(dx,dy)

 

 

근데 생각해보니까 서로 다른 두 점 (x1,y1), (x2,y2)가 동일한 이동 (dx,dy)에 대하여

 

동일한 점 (x3,y3)로 이동할 수 없기 때문에 visited로 체크할 필요는 없는 듯

 

그래서 각 이동 (dx,dy)에 대하여 A의 모든 점 (x,y)에 대해 이동시켜서 B에 속하는지 체크해보고

 

B에 속하는 점이 하나라도 없다면 no

 

이동한 점이 모두 B에 속하게 된다면 yes

 

from sys import stdin

m = int(stdin.readline())

A = []

for _ in range(m):
    
    x,y = map(int,stdin.readline().split())
    A.append((x,y))

n = int(stdin.readline())

B = {}

for i in range(n):
    
    x,y = map(int,stdin.readline().split())

    B[(x,y)] = i

delta = []

X = A[0][0]
Y = A[0][1]

for x,y in B:
    
    delta.append((x - X,y - Y))

for dx,dy in delta:
    
    no = False

    for i in range(m):
        
        x,y = A[i]

        if B.get((x + dx, y + dy),-1) == -1:
            
            no = True
            break
    
    if no == False:
        
        break

print(dx,dy)