HDU2036 , 任意多边形面积

hdu2036

开始我是选一个点然后对其他点遍历计算的面积之和, 但是这样只能计算凸多边形的面积; 于是就WA了

只有找任意多边形面积的计算方法来计算;

任意多边形的面积是用向量的方法来算的, 参考

这就记下来当个板子...

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 105;
int x[maxn], y[maxn];

// 这个只是求任意三个点组成的三角形的面积;
// double S(int i, int j, int k){
//     double x1 = x[k] - x[i], x2 = x[j] - x[i];
//     double y1 = y[k] - y[i], y2 = y[j] - y[i];
//     return abs(x1 * y2 - x2 * y1) * 1.0 / 2;
// }

// 求任意多边形的面积;
// 也是使用的向量的来算的, 和上面的计算三角形的面积原理其实是一样的;
double S(int x[],int y[],int n)
{
    int i,j;
    double s=0;
    for(i=0;i<n;i++){
        j=(i+1)%n;
        s+=x[i]*y[j];
        s-=x[j]*y[i];
    }
    s/=2;
    return s>0?s:-s;
}

int main(){
    int n;
    while(scanf("%d", &n) == 1 && n != 0){
        for(int i=0;i<n;i++){
            scanf("%d%d", &x[i], &y[i]);
        }
        double ans = S(x, y, n);
        printf("%.1lf\n", ans);
    }
    return 0;
}