laekov

本来以为是上回那道数正方形的原题的。结果发现不要求边与座标轴平行，于是我就naive了。然后数据结构变身计算几何一堆东西吼吼。

矩形的对角线相等且互相平分（来自初二数学书）。把所有点对的中点找出来，把所有相等且平分的放一起用单调性，有点像旋转卡(qia3)壳(qiao4)的做法。jason_yu说暴力枚举都能过，而且他跑得比我快！

计算几何也写得比较naive。调了半天啊。

毕竟我弱嘛。

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long qw;

#ifdef WIN32

#define lld "%I64d"

#else

#define lld "%lld"

#endif

#define _l (qw)

const double eps = 1e-8;

const int maxn = 1509;

#define sqr(x) ((x)*(x))

#define dist(a,b) (sqr(a.x-b.x)+sqr(a.y-b.y))

#define nextele(_x_) ((_x_+1==r)?(l):(_x_+1))

struct point {

qw x, y;

point(qw x0 = 0, qw y0 = 0) {

x = x0, y = y0;

}

inline point operator =(const point& a) {

x = a. x, y = a. y;

return *this;

}

};

struct vect {

qw x, y;

inline vect(qw x0 = 0, qw y0 = 0) {

x = x0, y = y0;

}

inline vect(point a, point b) {

x = b. x - a. x, y = b. y - a. y;

}

inline qw mulx(const vect& a) const {

return x * a. y - y * a. x;

}

inline vect operator =(const vect& a) {

x = a. x, y = a. y;

return *this;

}

inline void reverse() {

x = -x, y = -y;

}

};

struct mid_point {

qw x, y, l;

vect d;

inline mid_point() {

}

inline mid_point(point a, point b) {

x = (a. x + b. x) >> 1;

y = (a. y + b. y) >> 1;

l = dist(a, b);

d = vect(b. x - x, b. y - y);

if (d. x < 0)

d. reverse();

}

inline bool operator ==(const mid_point& a) {

return x == a. x && y == a. y && l == a. l;

}

inline mid_point operator =(const mid_point& a) {

x = a. x, y = a. y, l = a. l, d = a. d;

return *this;

}

};

inline bool cmpPoint(const point& a, const point& b) {

return a. x < b. x || (a. x == b. x && a. y < b. y);

}

inline bool cmpMPoint(const mid_point& a, const mid_point& b) {

return a. x < b. x || (a. x == b. x && a. y < b. y) || \

(a. x == b. x && a. y == b. y && a. l < b. l) || \

(a. x == b. x && a. y == b. y && a. l == b. l && a. d. mulx(b. d) > 0);

}

int n, t;

qw ans;

point a[maxn];

mid_point b[maxn * maxn];

int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif

ans = 0;

t = 0;

scanf("%d", &n);

for (int i = 0; i < n; ++ i) {

scanf(lld lld, &a[i]. x, &a[i]. y);

a[i]. x <<= 1;

a[i]. y <<= 1;

for (int j = 0; j < i; ++ j)

b[t ++] = mid_point(a[i], a[j]);

}

sort(b, b + t, cmpMPoint);

for (int l = 0, r; l < t; l = r) {

for (r = l + 1; r < t && b[r] == b[l]; ++ r);

if (r - l < 2)

continue;

for (int i = l, j = l; i < r; ++ i) {

if (j == i)

j = nextele(j);

while (b[i]. d. mulx(b[j]. d) < b[i]. d. mulx(b[nextele(j)]. d))

j = nextele(j);

ans = max(ans, abs(b[i]. d. mulx(b[j]. d)));

}

}

printf(lld "\n", ans >> 1);

}