[Python] 백준 9015번: 정사각형

https://www.acmicpc.net/problem/9015

9015번: 정사각형

 

 > 접근

시간 제한이 10초이고 N이 3000이므로 정사각형 판별을 어렵게 하지 않아도 된다고 생각했다. 우선 정사각형을 어떻게 판별할지에 대해 고민해보자.

위 사진과 같이 정사각형을 이루는 네 점들에서 특정한 패턴이 있다.

offset을 계산해보면 위와 같다. 패턴이 보이지 않는가? 현재 오프셋이 offset_x, offset_y라면, 그 다음 오프셋은 offset_y, -offset_x이다.

이 특징을 통해 정사각형을 판별하기 위해선 두 점이 필요하다. 따라서 N^2 반복문을 돌면서 정사각형 판별을 해주면 된다.

 

 > 풀이

정사각형 판별을 하기 위해 좌표계에 대해 정보가 필요할 것이다. N^2 반복문을 돌기 위해서 모든 점(x, y로 구성된)들을 포함한 리스트가 필요할 것이며, 특정 좌표에 점이 있는지 여부를 파악하기 위한 어떤 것이 필요하다. 여기서 후자를 위해서 초기에는 2차원 배열이 아닌, 이중 맵(m[x][y]와 같은 식으로 접근)을 사용하였고 이로써 메모리를 절약할 수 있었다.

하지만 set 하나만으로 이 문제를 풀 수 있었다. 문제에서 좌표의 범위가 매우 좁은 편이기 때문에 x, y 좌표로 구성된 점을 정수 하나로 치환할 수 있다.

INF = 10001

def convert_point_to_index(x, y):
  return INF*x + y

def convert_index_to_point(index):
  return index//INF, index%INF

 

a-z 문자를 0~25로 대응시키는 것과 비슷한 원리이다.

 

# -*- coding: utf-8 -*-
import sys, math
input = sys.stdin.readline
INF = 10001

def convert_point_to_index(x, y):
  return INF*x + y

def convert_index_to_point(index):
  return index//INF, index%INF

def get_area(x1, y1, x2, y2):
  return math.pow(x1 - x2, 2) + math.pow(y1 - y2, 2)

def solution():
  max_area = 0
  for index in points:                   
    max_area = max(max_area, get_max_area_at(*convert_index_to_point(index)))
    
  return int(max_area)

def get_max_area_at(x, y):
  res = 0
  for index in points:
    adj_x, adj_y = convert_index_to_point(index)

    offset_x, offset_y = adj_x - x, adj_y - y
    cur_x, cur_y = adj_x, adj_y      

    # (x,y) - (adj_x,adj_y) 직선을 포함하는 정사각형 찾기
    for _ in range(2):
      offset_x, offset_y = offset_y, -offset_x
      cur_x, cur_y = cur_x + offset_x, cur_y + offset_y     

      if(convert_point_to_index(cur_x, cur_y) not in points):
        break         
    else:                                                         
      res = max(res, get_area(x, y, adj_x, adj_y))

  return res
                                           
if __name__ == '__main__':
  for _ in range(int(input())):     
    points = {convert_point_to_index(*map(int, input().split())) for _ in range(int(input()))}                                    
    print(solution())