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