模板求凸包面积

深藏阁楼爱情的钟 2022-08-10 15:37 244阅读 0赞

#include <stdio.h>
    #include <iostream>
    #include <stdlib.h>
    #include <math.h>
    using namespace std;
    typedef struct
    {
        double x;
        double y;
    }point;
    point chs[50001],a[50001];     
    int sp,N,Q; 
    double s[50001];
    
    double dis(point a, point b)
    {
        return sqrt((a.x - b.x) * (a.x - b.x) * 1.0 + (a.y - b.y) * (a.y - b.y));
    }
    
    double multi(point p0, point p1, point p2)
    {
        return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
    }
    
       
    double findarea(int n)
    {
        int i;
        double area;
        area = 0.;
        for(i=1; i<n-1; i++) //求面积
        {
            double k = multi(a[0], a[i], a[i+1]); //三角形面积是向量叉积的1/2
            area += k;
    		s[i+1]=fabs(area)/2;
        }
        area = fabs(area) / 2;
        return area;
    }
    
    int main()
    {
    	int i,l,r,j;
    	double ans,anss,sum;
    	scanf("%d%d",&N,&Q);
    	s[0]=s[1]=0;
    	for (i=0;i<N;i++)
    		scanf("%lf%lf",&a[i].x,&a[i].y);
    	sum=findarea(N);
    	for (i=1;i<=Q;i++)
    	{
    		cin >> l >> r;
    		ans=s[r]-s[l]-fabs(multi(a[0], a[l], a[r]))/2;
    		anss=sum-ans;
    		if (ans>anss)
    			ans=anss;
    	     printf("%.1f\n",ans);
    	
    	}
    return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，244人围观）

还没有评论，来说两句吧...

相关阅读

相关 python实现open3d计算点云平面面积的凸包或者凹包面积

Open3D是一个用于3D数据处理的开源库，提供了多种功能和工具，其中包括点云处理。在本文中，我们将介绍如何使用Python中的Open3D库计算点云的凸包或凹包面积。 1.

约定不等于承诺〃/ 2024年03月16日 17:18/ 0 赞/ 140 阅读

相关 LuoGuP2742[模板]二维凸包

[LuoGuP2742\[模板\]二维凸包][LuoGuP2742] 如你所见,这是二维凸包的模板题. 我用的是水平序的\\(Andrew\\) 算法,是从毒瘤汝佳那里

谁践踏了优雅/ 2023年06月02日 11:59/ 0 赞/ 15 阅读

相关模板求凸包面积

include <stdio.h> include <iostream> include <stdlib.h> include <math.h>

深藏阁楼爱情的钟/ 2022年08月10日 15:37/ 0 赞/ 245 阅读

相关凸包及多边形面积

首先求多边形面积，这个比较简单，用的就是把一个多边形划分为多个三角形，然后求三角形面积。代码： double Cross(Vector A,Vector B) {

小咪咪/ 2022年08月10日 14:41/ 0 赞/ 294 阅读

相关二维凸包模板(Graham算法)

时间复杂度O(nlogn) 模板： include <cstdio> include <cmath> include <cstdlib>

矫情吗；*/ 2022年06月11日 09:26/ 0 赞/ 276 阅读

相关 POJ3528 (三维凸包模板)

Ultimate Weapon [POJ - 3528 ][POJ - 3528] In year

野性酷女/ 2022年06月11日 09:12/ 0 赞/ 281 阅读

相关 POJ 3348(计算几何+二维凸包+多边形面积)

问题描述: Your friend to the south is interested in building fences and turning plowshares

蔚落/ 2022年06月08日 11:49/ 0 赞/ 293 阅读

相关 POJ - 3348 Cows(求凸包的面积)

[点我看题][Link 1] 题意:一片草原上有n棵树,给出这n棵树的坐标,准备用其中的一些树围成一个多边形,每只奶牛要吃掉50m^2的草,问围成的草坪可供多少只奶牛. 分

迈不过友情╰/ 2022年06月07日 06:58/ 0 赞/ 205 阅读

相关 OpenCV凸包凸缺陷检测

![20170930235136628][] 左边原图，右边结果。右图中，蓝色线为凸包，凸缺陷的起始点为黑色点，凸缺陷的起始点为绿色点，凸缺陷的最深点为红色点（即边缘点到

逃离我推掉我的手/ 2022年06月07日 00:43/ 0 赞/ 601 阅读

相关 UVA - 10652 Board Wrapping （凸包+多边形面积）

include<cstdio> include<cmath> include<iostream> include<algorithm>

快来打我*/ 2022年05月27日 09:05/ 0 赞/ 280 阅读