백준9015 정사각형

작성일 | In

문제 링크

  • http://icpc.me/9015

문제 출처

  • 2012 ACM-ICPC 대전 인터넷 예선 J번

시간복잡도

  • O(n2 log n)

풀이

n 제한이 최대 3000이기 때문에 O(n3)보다는 빠른 복잡도를 가진 알고리즘을 고안해내야 합니다.
이 문제는 이데일리 코딩 챌린지 예선에 잘못된 데이터와 함께 나왔던 문제이기 때문에 쉽게 풀 수 있었습니다.

정사각형은 모든 각이 90도이며 모든 변의 길이가 동일합니다. 이 점을 이용해 O(n2 log n2) 정도의 알고리즘을 만들 수 있습니다.
먼저 아무 두 점을 잡고, 그 두 점의 좌표를 각각 (x1, y1), (x2, y2)라고 잡읍시다. 또한 계산의 편의를 위해 x1-x2를 a, y1-y2를 b라고 합시다.
만약 주어진 점들 중 (x1+b, y1-a)와 (x2+b, y2-a)의 좌표를 가진 점이 모두 있다면, 네 점을 이어 정사각형을 만들 수 있습니다.
아무 두 점을 잡는데 O(n2)이 걸리고, set을 이용한다면 특정 좌표에 점이 있는지는 O(log n)에 구할 수 있습니다.

다만, set의 구현체인 Red-Black Tree는 시간 복잡도의 상수가 매우 커서 데이터가 많으면 시간 초과가 날 수 있기 때문에 데이터를 적절히 분산해서 넣어주어야 합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;

set<int> s[20010];
int a, b, n, ret;

inline bool can(int n){
	if(n<0 || n>=20010) return 0;
	return 1;
}

void solve(){
	int n; cin >> n;
	vector<p> v(n);
	for(int i=0; i<20010; i++) s[i].clear();
	for(int i=0; i<n; i++){
		int a, b; cin >> a >> b;
		a += 10000; b += 10000;
		v[i] = {a, b};
		s[v[i].first].insert(v[i].second);
	}
	int ans = 0;
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			p p1 = v[i], p2 = v[j];
			int x1 = p1.first, y1 = p1.second;
			int x2 = p2.first, y2 = p2.second;

			int a = x1-x2, b = y1-y2;

			int x3 = x1+b, y3 = y1-a;
			int x4 = x2+b, y4 = y2-a;

			if(!can(x3) || !can(y3) || !can(x4) || !can(y4)) continue;

			if(s[x3].count(y3) && s[x4].count(y4)){
				ans = max(ans, a*a + b*b);
			}
		}
	}
	cout << ans << "\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--){
		solve();
	}  
}