计算几何

我们先把所有的线段求出来，我们发现只有两个线段等长且中点重合时才能构成矩形，那么线段有n*n条，我们按中点，长度排序，然后对于一条线段扫描所有符合条件的线段计算答案，这样看起来是O(n^3)次的，实际上远远到不了

但是1336和1765两道题空间较小，不能乱开空间

#include
using namespace std;
const int N = ;
int n;
double ans;
int x[N], y[N];
struct line {
int mx, my, x1, x2, y1, y2;
long long len;
bool friend operator < (line A, line B) { if(A.mx != B.mx) return A.mx < B.mx; if(A.my != B.my) return A.my < B.my; if(A.len != B.len) return A.len < B.len; return true; } line(int mx, int my, long long len, int x1, int y1, int x2, int y2) : mx(mx), my(my), len(len), x1(x1), y1(y1), x2(x2), y2(y2) {} }; vector v;
inline long long sqr(long long x) { return x * x; }
inline double Area(line a, line b)
{
double disa = sqrt(sqr(a.x1 - b.x1) + sqr(a.y1 - b.y1)), disb = sqrt(sqr(a.x2 - b.x1) + sqr(a.y1 - b.y2));
return disa * disb;
}
int main()
{
// freopen("crectangle.in", "r", stdin);
// freopen("crectangle.out", "w", stdout);
scanf("%d", &n);
for(int i = ; i <= n; ++i) scanf("%d%d", &x[i], &y[i]); for(int i = ; i <= n; ++i) for(int j = i + ; j <= n; ++j) { long long len = sqr(x[i] - x[j]) + sqr(y[i] - y[j]); v.push_back(line(x[i] + x[j], y[i] + y[j], len, x[i], y[i], x[j], y[j])); } sort(v.begin(), v.end()); for(int i = ; i < v.size(); ++i) { line a = v[i]; for(int j = i - ; j >= ; --j)
{
line b = v[j];
if(a.mx != b.mx || a.my != b.my || a.len != b.len) break;
ans = max(ans, Area(a, b));
}
}
printf("%.0f\n", ans);
// fclose(stdin);
// fclose(stdout);
return ;
}