백준 2415 - 직사각형
https://www.acmicpc.net/problem/2415
문제
좌표 평면에 N (4 ≤ N ≤ 1,500) 개의 점이 주어진다.
서로 다른 점 4개를 선택하면 사각형을 만들 수 있다. 이러한 사각형 중에 직사각형인 것 중 넓이가 가장 큰 것을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 점의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 점의 좌표 x y가 주어진다. 점의 좌표는 -10^8보다 크거나 같고, 10^8보다 작거나 같은 정수이다. 점의 좌표는 중복되지 않는다.
출력
가장 큰 직사각형의 넓이를 출력한다.
풀이
$\binom{1500}{4} \approx 2.1 \times 10^{11}$이므로 탐색 수를 줄여야 한다.
직사각형의 두 대각선은 길이가 같고 서로를 이등분한다. 따라서, 중심과 길이가 같은 두 선분의 꼭짓점을 이으면 직사각형을 만들 수 있다. 이 점을 이용해, 주어진 점들로 만들 수 있는 모든 선분에 대해 길이와 중심점이 같은 것을 묶어 선분 집합을 만들면 가능한 직사각형을 전부 구할 수 있다. 이 작업은 길이, 중심 좌표 순으로 정렬하는 것으로 처리할 수 있다. 따라서 위 과정은 $O(n^2)$이다.
이제 각 집합에 대해 넓이의 최댓값을 구하면 된다. 선분 집합의 원소 수가 $m$일 때 넓이가 가장 큰 두 쌍을 고르는 작업은 $O(m^2)$이다. 최악의 경우, 즉 $m$이 최대가 되는 경우는 모든 점이 하나의 원 위에 있는 경우 $n/2$개의 선분이 생기는 것이므로 이 작업 역시 $O(n^2)$이다.
선분을 나타내는 struct를 만들고, 몇 번째 점을 이은 선인지, 중심의 x와 y 좌표는 무엇인지, 길이는 무엇인지 담도록 하였다. 점은 x와 y 좌표만 필요하므로 같은 struct를 이용하였다.
코드
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct line{
ll i, j, x, y, l;
};
vector<line> pts, lines;
bool cmp(line l1, line l2){
if (l1.l != l2.l) return l1.l < l2.l;
if (l1.x != l2.x) return l1.x < l2.x;
return l1.y < l2.y;
}
ll area(line l1, line l2){
line p1 = pts[l1.i], p2 = pts[l1.j], p3 = pts[l2.i];
return abs(((p1.x * p2.y) + (p2.x * p3.y) + (p3.x * p1.y)) - ((p1.y * p2.x) + (p2.y * p3.x) + (p3.y * p1.x)));
}
int main(){
int n; cin >> n;
for (int i = 0; i < n; i++){
ll x, y; cin >> x >> y;
pts.push_back({0, 0, x, y, 0});
}
ll xi, xj, yi, yj;
for (int i = 0; i < n; i++){
xi = pts[i].x; yi = pts[i].y;
for (int j = i + 1; j < n; j++){
xj = pts[j].x; yj = pts[j].y;
lines.push_back({i, j, xi + xj, yi + yj, (xi - xj) * (xi - xj) + (yi - yj) * (yi - yj)});
}
}
sort(lines.begin(), lines.end(), cmp);
ll result = 0;
for (int i = 0; i < lines.size(); i++){
for (int j = i + 1; (j < lines.size()) && (lines[i].l == lines[j].l) && (lines[i].x == lines[j].x) && (lines[i].y == lines[j].y); j++){
result = max(result, area(lines[i], lines[j]));
}
}
cout << result;
}