HDU---2036

待我称王封你为后i 2022-08-11 13:30 21阅读 0赞

一道计算几何的题目：

首先想到的是三角形分割，但是觉得三角形分割做法可能有些繁琐，而且最后仔细想想如果我选择的多边形是

凹多边形怎么办？不过还好有矢量的叉积运算，可以方便的算出三角形的面积，由此衍生出的多边形的面积的求法。这是从维普上找的别人的文献，其实自己退也很简单。

![Image 1][]

之后又查了查，因为所给的点都是整数点，因此该题也可用[皮克公式][Link 1]求解，只不过比较麻烦的是如何求出多边形内部的整数点的个数，思来想去发现这种方法还是没有根据叉乘推出的公式简便。但是这也是一种思路，或许做了这一题后不久又碰到一题让我统计给定顶点的多边形内部的整数点的个数，那我就哭笑不得了。

多边形公式代码：

#include <cstdio>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    struct point 
    {
    	int x,y;
    	void read()
    	{
    		scanf("%d%d",&x,&y);
    	}
    }vertex[100];
    
    
    int main()
    {
    	int n;
    	while(scanf("%d",&n)==1&&n)
    	{
    		double area=0;
    		vertex[0].read();
    		for(int i=1;i<n;i++)
    		{
    			vertex[i].read();
    			area+=1.0*(vertex[i-1].x*vertex[i].y-vertex[i].x*vertex[i-1].y);
    		}
    		area+=1.0*(vertex[n-1].x*vertex[0].y-vertex[0].x*vertex[n-1].y);
    		area/=2.0;
    		printf("%.1lf\n",area);
    	}
    	return 0;
    }

[Image 1]: 
[Link 1]: http://zh.wikipedia.org/zh-cn/%E7%9A%AE%E5%85%8B%E5%AE%9A%E7%90%86

发表评论取消回复

表情：

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

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

相关阅读

相关 P2036 [COCI2008-2009#2] PERKET

[题目][Link 1] Perket 是一种流行的美食。为了做好 Perket，厨师们必须小心选择配料，以便达到更好的口感。你有N种可支配的配料。对于每一种配料，我们知道

野性酷女/ 2023年02月17日 03:38/ 0 赞/ 16 阅读

相关 QT QSqlError(“2036“, “QMYSQL3: Unable to bind value“）解决

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录完整问题描述一、tableView控件插入数据失败 1.错误描述

ゞ浴缸里的玫瑰/ 2022年12月27日 01:42/ 0 赞/ 183 阅读

相关【杭电oj2036】改革春风吹满地

改革春风吹满地 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Othe

墨蓝/ 2022年09月25日 06:29/ 0 赞/ 132 阅读

相关 hdu 题目2034（水题），2036（水，简单计算多边形面积）,2037(水，贪心，会场安排类)

[http://acm.hdu.edu.cn/showproblem.php?pid=2034][http_acm.hdu.edu.cn_showproblem.php_pid

Dear 丶/ 2022年09月17日 11:20/ 0 赞/ 193 阅读

相关杭电2036-改革春风吹满地

改革春风吹满地 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Othe

一时失言乱红尘/ 2022年08月19日 02:12/ 0 赞/ 57 阅读

相关 HDU---2036

一道计算几何的题目：首先想到的是三角形分割，但是觉得三角形分割做法可能有些繁琐，而且最后仔细想想如果我选择的多边形是凹多边形怎么办？不过还好有矢量的叉积运算，可以方便的

待我称王封你为后i/ 2022年08月11日 13:30/ 0 赞/ 22 阅读

相关 hdu 2112 ——HDU Today

Problem Description 经过锦囊相助，海东集团终于度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发

朴灿烈づ我的快乐病毒、/ 2022年08月09日 13:46/ 0 赞/ 257 阅读

相关 HDU - 2112 - HDU Today

-------------------- 题目连接：[http://acm.hdu.edu.cn/showproblem.php?pid=2112][http_acm.hdu

布满荆棘的人生/ 2022年06月12日 10:40/ 0 赞/ 244 阅读

相关 HDU_2036改革春风吹满地

求凸多边形面积一个n多边形可以分解为 (n-2) 个三角形然后再算这 (n-2) 个三角形的面积之和就行了其实就是向量的叉乘 ![70][] ![70 1

朴灿烈づ我的快乐病毒、/ 2022年05月27日 00:49/ 0 赞/ 97 阅读

相关 kmp1-HDU1711 HDU1686 HDU2087 HDU3746

HDU 1711 kmp模板题 [http://acm.hdu.edu.cn/showproblem.php?pid=1711][http_acm.hdu.edu.cn_sh

叁歲伎倆/ 2022年05月14日 11:24/ 0 赞/ 249 阅读