首页 > 其他分享 >计算面积

计算面积

时间:2024-08-12 21:15:50浏览次数:11  
标签:凸多边形 return point int top 面积 凸包 计算

1 面积最大的三角形

https://vjudge.net/contest/647024#problem/A

凸包

https://www.cnblogs.com/aiguona/p/7232243.html

代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n,top;
struct point
{
	double x,y;
} p[N], s[N];
/*它是点集的最小凸边界。所有点都在
这个多边形的内部或边界上。
给定一个点集,凸包是包含所有这些点的最小凸多边形
这个三角形的一个或多个顶点在凸包的边界上
给定点集,计算凸包可以显著减少点的数量*/

bool cmp(point a, point b)

{
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
	//按照x,y从小到大排序,升序 
	//找到凸包的第一个点 
}


double cross(point a, point b, point c) //叉积
{
	//三角形面积=1/2叉积的绝对值 ,叉积为正,c在ab右侧,a到b转弯到c逆时针,为0三点共线 
	//凸多边形:对于凸多边形上的任意两点 A 和 B,多边形的边界内的点 
//C 必须在AB 的左侧(逆时针方向),保持多边形的凸性。
	return (b.x - a.x) *(c.y- a.y) - (c.x- a.x) * (b.y - a.y);
}


signed main()
{
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++)
		scanf("%lf%lf", &p[i].x,&p[i].y);

	sort(p +1, p +1 + n,cmp);
	
	//下凸包,模拟栈构造,top栈顶,凸包的点数 
	top=0;
	for(int i=1; i<=n; i++)
	{
		while (top > 1 && cross(s[top - 1], s[top], p[i]) <= 0) --top ;
		s[++top] = p[i];
		/*如果叉积值小于或等于 0,说明 p[i] 与当前边的方向不符,可能使当前边向内弯曲,因此需要移除当前边。*/
	}

//上凸包 
	int t = top;
	for (int i = n - 1; i >= 1; i -- )
	{
		while (top > t && cross(s[top - 1], s[top], p[i]) <= 0) --top ;
		s[++top] = p[i];
	}


	n = top - 1;
	double ans = 0;
	double S = 0;
	
	for (int i = 1; i <= n; i++)
	{
		int a = i, b=i +1;
		for (int j = i + 1; j <= n; j++)
		{
			while (cross(s[i], s[j], s[a + 1]) < cross (s[i], s[j], s[a])) a = a % n+1;
			S = max(S, 0.5 * -cross(s[i], s[j], s[a]));
		}
	}
	printf("%.9lf", S);
}

标签:凸多边形,return,point,int,top,面积,凸包,计算
From: https://www.cnblogs.com/hoshino-/p/18355763

相关文章

  • 计算机体系结构技术杂谈(上)
    计算机体系结构技术杂谈(上)2.1计算机的层次结构2.1.1基本概念介绍1.计算机基本概念1)机器数:用0和1编码的计算机内部的0/1序列。2)真值:机器数真正的值,即:现实中带正负号的数(通常指带符号二进制数对应的真正的数值)。3)定点数:将一个实数表示为带有固定小数点位置的整数,这个小数......
  • 计算机毕业设计django+vue代驾服务【开题+论文+程序】
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景随着城市化进程的加速和汽车保有量的持续增长,代驾服务作为一种便捷、安全的出行方式,逐渐受到广大消费者的青睐。然而,传统的代驾服务模式往......
  • 计算机毕业设计django+vue民宿预定管理系统625l0【开题+论文+程序】
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景随着互联网技术的迅猛发展和旅游业的不断壮大,民宿作为旅游住宿的重要组成部分,其市场需求日益增加。然而,传统的民宿管理方式已难以满足日益......
  • 基于flask+vue框架的高校毕业生在线招聘系统[开题+论文+程序]-计算机毕设
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景随着高等教育的普及与就业市场的日益竞争激烈,高校毕业生面临着前所未有的求职挑战。传统招聘方式受限于时间、地域等因素,难以高效匹配企业......
  • 基于flask+vue框架的畅饮水站业务管理系统[开题+论文+程序]-计算机毕设
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景随着现代生活节奏的加快与健康意识的提升,便捷、高质量的饮用水服务成为了人们日常生活中不可或缺的一部分。畅饮水站作为社区及办公区域的......
  • 【计算机毕设选题】2025年计算机毕业设计选题 200个热门毕设题目推荐
    ......
  • 基于django+vue基于web的园区车辆出入管理系统【开题报告+程序+论文】计算机毕设
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景随着城市化进程的加快,各类产业园区、住宅小区及商业综合体等园区规模不断扩大,车辆管理成为园区管理中的重要环节。传统的车辆出入管理方式......
  • Java计算机毕业设计的酒店管理系统的设计与实现(开题+源码+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着信息技术的飞速发展和党组织建设的日益规范化,传统的手工党员管理模式已难以满足当前高效、精准的管理需求。特别是在高校、企事业单位等组织中,党......
  • Java计算机毕业设计的爱心慈善公益系统(开题+源码+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景在当今社会,随着经济的快速发展与人民生活水平的普遍提高,社会各界对于公益慈善事业的关注与参与度日益增强。然而,传统的慈善模式往往受限于信息不对称......
  • Java计算机毕业设计的汽车配件管理系统的设计与实现(开题+源码+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着汽车工业的迅猛发展,汽车配件市场日益繁荣,配件种类繁多、更新换代迅速,给汽车售后服务和维修行业带来了前所未有的挑战。传统的手工或简单电子化的......