2415번: Rectangle

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


$O(n^2(C+\lg n))$

네 점이 직사각형을 이룰 필요충분조건은
마주보는 점을 연결하여 만든 두 선분의 길이와 그 절반에 위치한 중심이 일치하는 것이다.
이를 이용해 임의의 두 점에 대해 선분을 만들어 (길이, 중심점)이 같은 쌍끼리 모아서 최대 직사각형을 찾으면 된다.

주어진 점들 좌표가 정수이므로 중심점과 이로부터 거리(r)가 같은 점들은 그리 많지 않다.
(http://math.stackexchange.com/questions/17496/number-of-integer-solutions-of-x2-y2-k)
그래서 중심점, r이 같은 모든 선분쌍에 대해 직사각형을 만들어보며 최대 넓이를 찾아도 괜찮다.

#include<cstdio>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> point;
const int MXN = 1500;
int n, sz;
ll r;
point p[MXN];
pair<pair<point, ll>, point> a[MXN*MXN];
ll dis(point i, point j) {
    return (ll)(i.x - j.x)*(i.x - j.x) + (ll)(i.y - j.y)*(i.y - j.y);
}
ll ccw(point i, point j) {
    return (ll)i.x*j.y - (ll)i.y*j.x;
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &p[i].x, &p[i].y);
        for (int j = 0; j < i; j++) a[sz++] = { { { p[i].x + p[j].x,p[i].y + p[j].y },dis(p[i],p[j]) },{ p[i].x - p[j].x,p[i].y - p[j].y } };
    }
    sort(a, a + sz);
    for (int i = 0; i < sz; i++)
        for (int j = i; j < sz&&a[i].x == a[j].x; j++) r = max(r, abs(ccw(a[i].y, a[j].y)));
    printf("%lld", r / 2);
    return 0;
}

$O(n^2\lg n)$

(길이, 중심점)이 같은 선분들에 대해

중심점을 기준으로 끝점들을 시계방향 정렬한 뒤 넓이를 가지고 inchworm 알고리즘을 돌려도 된다.

#include<cstdio>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> point;
typedef pair<pair<point, ll>, point> tp;
const int MXN = 1500;
int n, sz;
ll r;
point p[MXN];
tp a[MXN*MXN];
ll dis(point i, point j) {
    return (ll)(i.x - j.x)*(i.x - j.x) + (ll)(i.y - j.y)*(i.y - j.y);
}
ll ccw(point i, point j) {
    return (ll)i.x*j.y - (ll)i.y*j.x;
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &p[i].x, &p[i].y);
        for (int j = 0; j < i; j++) {
            int dx = p[i].x - p[j].x, dy = p[i].y - p[j].y;
            if (dx < 0) dx *= -1, dy *= -1;
            a[sz++] = { { { p[i].x + p[j].x,p[i].y + p[j].y },dis(p[i],p[j]) },{ dx,dy } };
        }
    }
    sort(a, a + sz, [](tp i, tp j) {return i.x < j.x || i.x == j.x&&ccw(i.y, j.y)>0; });
    for (int i = 0, j; i < sz; i++) {
        if (!i || a[i - 1].x != a[i].x) j = i;
        while (j + 1 < sz&&a[i].x == a[j + 1].x&&ccw(a[i].y, a[j].y) < ccw(a[i].y, a[j + 1].y)) j++;
        r = max(r, ccw(a[i].y, a[j].y));
    }
    printf("%lld", r / 2);
    return 0;
}