题目链接

 /*
Name:nyoj-952-最大四边形
Copyright:
Author:
Date: 2018/4/27 10:46:24
Description:
枚举一条对角线,再选择一个
看大佬们的解释,在二维向量中,叉乘的结果(仍是向量)等于面积
利用叉乘求三角形面积,点的顺时针,
逆时针的正负不同,知道这个点在对角线的哪侧,
分别求出各侧面积的最大的,俩个相加,就为这条对角线所获的最大四边形面积
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const double eps = 1e-;
struct node{
double x ,y;
} arr[];
double cross(node a,node b1,node b2){//求(b1-a) 和(b2-a) 的叉乘
double x1,y1,x2,y2;
x1=b1.x-a.x;
y1=b1.y-a.y;
x2=b2.x-a.x;
y2=b2.y-a.y;
return x1*y2-x2*y1;
}
int main()
{
int n;
while (cin>>n) {
memset(arr, , sizeof(arr));
for (int i=; i<n; i++) {
cin>>arr[i].x>>arr[i].y;
}
double lmax = , rmax = , area = ;
for (int i=; i<n; i++) {
for (int j=i+; j<n; j++) {
lmax = , rmax = ;//如果向量结果为负,取最大值还是0,当然左右是一负一正
for(int k=; k<n; k++) {
if (k != i && k!= j){
/*
分别求出对角线两边的最大面积,向量点乘求出对角线一侧的面积
在没有除以2的时候,求得是平行四边形的面积 求出左右面积最大的情况相加,就是最大的两个平行四边形的面积,
除以2,就是将对角线相同的两个平行四边形各取一半拼起来的最大情况
*/
double tmp = cross(arr[i], arr[j], arr[k]);
lmax = max(lmax, tmp);
rmax = max(rmax, -tmp);
}
}
if(lmax <= eps || rmax <= eps) continue;
area = max(area, lmax + rmax);
}
}
printf("%lf\n", area / );
}
return ;
}

最新文章

  1. loadrunner用javavuser进行接口测试
  2. 如何成为一名优秀的前端工程师 (share)
  3. ES6 - promise对象
  4. Rsync原理介绍及配置应用
  5. C4D to Unity3D插件C2U Tool开源发布!简化你的工作流
  6. 百度地图API示例之添加自定义控件
  7. 软件工程 speedsnail 第二次冲刺3
  8. 理解Mysql的索引与优化
  9. bzoj4330:JSOI2012 爱之项链
  10. MySql安装与卸载
  11. Bigcommerce:安装的出错解决方案
  12. CVTE C/C++开发工程师笔试题(一)
  13. [PDFBox]后台操作pdf的工具类
  14. iOS之加载Gif图片
  15. PHP判断用户是否手机访问
  16. 阿里云ECS服务器源配置
  17. vue播放video插件vue-video-player实现hls, rtmp播放全过程
  18. 【Python】python3-list列表引用
  19. Educational Codeforces Round 44 (Rated for Div. 2) F - Isomorphic Strings
  20. MD5加密概述

热门文章

  1. 剑指offer 面试9题
  2. 剑指offer 面试23题
  3. 【转】Python爬虫_示例
  4. 解决eclipse不识别Android手机的问题
  5. css系列(7)成品网页
  6. layer满屏/禁止最大化最小化 可以做选择框使用
  7. Android BlueDroid(蓝牙协议栈)
  8. Django框架之自定义分页
  9. LVS 命令使用
  10. 什么是make config,make menuconfig,make oldconfig,make xconfig,make defconfig,make gconfig?【转】