[BOJ] 25279 - Treehouse

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

BOJ - Treehouse

문제 유형: 기하학, 수학, 해시

문제 난이도: Gold III

시간 제한: 3초

메모리 제한: 1024MB

 

문제

Pusheen wants to build a treehouse in the Treehouse forest in Brunnshög in the north of Lund. The treehouse should to be built on a square platform in the treetops, with a tree in each of the four corners. When Pusheen has picked a spot to built the treehouse, trees that are located between the corners will be cut down. Pusheen has a 2D map with all the (x, y)-coordinates of the trees in the forest. In how many places can they build a square treehouse?

 

Pusheen이 스웨덴 룬드 북쪽의 Brunnshög에 있는 Treehouse Forest에서 나무 위 오두막을 지으려고 합니다. 오두막은 treetops(나무 꼭대기)에 있는 정사각형 플랫폼 위에 지어져야 하며, 플랫폼의 네 개의 꼭짓점에 각각 한 그루의 나무가 있어야 합니다.

 

Pusheen이 오두막을 지을 위치를 선택하면, 꼭짓점 사이에 있는 나무들은 잘라내게 됩니다.

 

Pusheen은 숲의 모든 나무들의 (x, y) 좌표가 표시된 2D 지도를 가지고 있습니다.

Pusheen이 정사각형 오두막을 지을 수 있는 가능한 위치의 개수를 구하세요.

 

입력

The first line has an integer 4≤N≤2000, the number of trees in the forest. Each of the following N lines has two integers −10,000≤xi,yi≤10,000, the x- and y-coordinates of tree i. All points are distinct.

 

첫째 줄에 점의 개수 N이 주어집니다.

이후의 N개의 줄에 각각 i번째 점의  x, y 좌표가 공백으로 구분되어 주어집니다.

 

출력

An integer, the number of suitable spots for a tree house.

오두막의 적절한 장소의 개수를 구하시오.

 

풀이

하나의 선분이 정해지면, 나머지 두 꼭짓점 조합은 두 가지로 좁혀진다.

그리고 그 두 꼭짓점은 각각 그 하나의 선분으로부터 수직이어야 한다.

위 그림에서 (3, 1)에서 (7, 3)선분을 주목하자.

 

그래서, 선분의 양 끝점 기준에서 선분과 같은 거리이고 시계방향으로 90도 각도에 있는 점 둘,

반시계방향으로 90도에 있는 점 둘이 후보가 된다.

각 쌍별로 실제 존재하는 점인지 확인한다.

점의 존재 여부는 해시맵으로 알 수 있다.

 

그러나, 2차원 루프를 돌다보면, 중복되게 계산한다는 것을 알 수 있다.

정사각형의 변이 4개이므로, 모든 조합을 보면 실제 개수 * 4개가 카운트된다.

4를 최종적으로 나눠주면 된다.

 

코드

C++

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

struct PairHash {
  size_t operator()(const pii &p) const {
    return hash<int>()((ll)p.first) ^ (hash<int>()((ll)p.second) << 32);
  }
};

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;

  vector<pii> points(n);
  unordered_set<pii, PairHash> pointSet;
  for (int i = 0; i < n; ++i) {
    int a, b;
    cin >> a >> b;
    points[i] = {a, b};
    pointSet.insert(points[i]);
  }

  int ans = 0;

  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      int x1 = points[i].first, y1 = points[i].second;
      int x2 = points[j].first, y2 = points[j].second;
      int dx = x2 - x1;
      int dy = y2 - y1;

      pii p3 = {x1 - dy, y1 + dx};
      pii p4 = {x2 - dy, y2 + dx};
      if (pointSet.find(p3) != pointSet.end() &&
          pointSet.find(p4) != pointSet.end()) {
        ans++;
      }

      p3 = {x1 + dy, y1 - dx};
      p4 = {x2 + dy, y2 - dx};

      if (pointSet.find(p3) != pointSet.end() &&
          pointSet.find(p4) != pointSet.end()) {
        ans++;
      }
    }
  }

  cout << ans / 4 << "\n";
  return 0;
}

 

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

type Point struct {
	x int32
	y int32
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int32
	fmt.Fscan(reader, &n)

	points := make([]Point, n)
	pointMap := make(map[Point]bool)

	for i := int32(0); i < n; i++ {
		var x, y int32
		fmt.Fscan(reader, &x, &y)

		points[i] = Point{x, y}
		pointMap[points[i]] = true
	}

	ans := int32(0)
	for i := int32(0); i < n; i++ {
		for j := i + 1; j < n; j++ {
			x1 := points[i].x
			y1 := points[i].y
			x2 := points[j].x
			y2 := points[j].y

			dx := x2 - x1
			dy := y2 - y1

			p3 := Point{x1 - dy, y1 + dx}
			p4 := Point{x2 - dy, y2 + dx}

			if _, ok1 := pointMap[p3]; ok1 {
				if _, ok2 := pointMap[p4]; ok2 {
					ans++
				}
			}

			p3.x = x1 + dy
			p3.y = y1 - dx
			p4.x = x2 + dy
			p4.y = y2 - dx

			if _, ok1 := pointMap[p3]; ok1 {
				if _, ok2 := pointMap[p4]; ok2 {
					ans++
				}
			}
		}
	}

	fmt.Fprintln(writer, ans/4)
}