http://acm.hdu.edu.cn/showproblem.php?pid=2036
多边形面积公式推导：
使用二维向量求三角形的面积：对于三角形ABC 
文章图片
该题目中，取原点为三角形的一个点。
二维向量的叉乘公式为：
文章图片
文章图片
如果A(x1,y1),B(x2,y2),那么S=(x1*y2-x2*y1) / 2
得出多边形的计算公式：
文章图片
【ACM OJ 2036 多边形面积计算】（由于叉乘有正负，可处理凹多边形的情况）
#include
#include
#include
#include
using namespace std;
struct point{
int x;
int y;
};
int main(){
int n;
vector p;
point temp;
double area;
while(cin >> n){
p.clear();
area = 0.0;
if(n == 0){
break;
}
else{
for(int i = 0; i < n; i++){
cin >> temp.x;
cin >> temp.y;
p.push_back(temp);
}
}
for(int i = 0; i < p.size() - 1; i++){
area += 0.5*(p[i].x * p[i+1].y - p[i+1].x * p[i].y);
}
area += 0.5*(p[p.size()-1].x * p[0].y - p[0].x * p[p.size()-1].y);
area = area >= 0 ? area: -area;
printf("%.1lf\n",area);
}
return 0;
}
推荐阅读
- ACM|HDU 5322 Hope (CDQ分治+NTT)
- 牛客算法周周练15——A、B
- Codeforces Round #609 (Div. 2)——C. Long Beautiful Integer（思维）
- FZU - 2107题解
- #|【牛客】牛客练习赛67-E-牛妹游历城市——位运算优化
- ACM|回文树（自动机）（练习和总结）
- acm|扩展欧几里德算法(附证明)
- ACM|[dsu] codeforces 375D. Tree and Queries
- ACM|codeforces 732-D. Exams （二分）