题目描述


题解

计算几何

由于对角线平分且相等的四边形是矩形,因此我们可以把每条对角线存起来,按照对角线长度和中点位置为关键字排序,这样对于每个相同长度和中点的对角线就排到了一起。

于是对于每段可能形成矩形的区间暴力即可。

时间复杂度$O(cnt)$,$cnt$为矩形个数。根据大爷讲的某定理,$cnt<O(n^2\sqrt n)$,可以A掉本题。

注意本题任何时候都不能使用double,否则炸精度无限WA。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1510
using namespace std;
typedef long long ll;
struct data
{
ll len , px , py , dx , dy;
bool operator<(const data &a)const {return len == a.len ? px == a.px ? py < a.py : px < a.px : len < a.len;}
}a[N * N];
ll x[N] , y[N];
int tot;
ll calc(int i , int j)
{
return abs(a[i].dx * a[j].dy - a[i].dy * a[j].dx) >> 1;
}
int main()
{
int n , i , j , k , l;
ll ans = 0;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ )
{
scanf("%lld%lld" , &x[i] , &y[i]);
for(j = 1 ; j < i ; j ++ )
{
a[++tot].len = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
a[tot].px = x[i] + x[j] , a[tot].py = y[i] + y[j];
a[tot].dx = x[i] - x[j] , a[tot].dy = y[i] - y[j];
}
}
sort(a + 1 , a + tot + 1);
for(i = j = 1 ; i <= tot ; i = j)
{
while(a[j].len == a[i].len && a[j].px == a[i].px && a[j].py == a[i].py) j ++ ;
for(k = i ; k < j ; k ++ )
for(l = k + 1 ; l < j ; l ++ )
ans = max(ans , calc(k , l));
}
printf("%lld\n" , ans);
return 0;
}

最新文章

  1. TFS源代码管理的8大注意事项
  2. CSS3总结 (帅哥)
  3. 学习js回调函数
  4. jQuery Mobile 列表视图(带有自动检索)
  5. WeX5 快速开发平台 V3.6 正式版发布
  6. NGINX下配置404错误页面的方法分享
  7. hdu 2081
  8. 初识 css3中counter属性
  9. 安装Hadoop系列 — eclipse plugin插件编译安装配置
  10. angularJS $resource与后台restapi的对应关系
  11. cocos2d-x设计模式发掘之五:防御式编程模式
  12. cocos2dx arpg单机手游
  13. Seoer,牵起用户与搜索引擎双手的魔术师
  14. php 学习笔记 一
  15. python基础之常用关键字总结
  16. mysql修改表结构语句
  17. Hbase记录-Hbase其他工具
  18. Java并发编程--并发容器之Collections
  19. java多线程快速入门(十四)
  20. mysql命令行查看建表语句

热门文章

  1. Mandelbrot图像
  2. 为Oracle Clusterware修改公用及私有网络接口
  3. IO流_File类
  4. k8s1.13.0二进制部署-master节点(三)
  5. Yum简单使用小结
  6. Maven各种常用架包配置文件,保存一份
  7. debian常用指令
  8. virtualvenv+django+uWSGI+nginx 部署 踩坑记录
  9. Return Largest Numbers in Arrays-freecodecamp算法题目
  10. NOIP模拟赛 密室逃脱