2036 改革春风吹满地

Problem Description

“ 改革春风吹满地,
不会AC没关系;
实在不行回老家，
还有一亩三分地。
谢谢!（乐队奏乐）”

话说部分学生心态极好，每天就知道游戏，这次考试如此简单的题目，也是云里雾里，而且，还竟然来这么几句打油诗。
好呀，老师的责任就是帮你解决问题，既然想种田，那就分你一块。
这块田位于浙江省温州市苍南县灵溪镇林家铺子村，多边形形状的一块地，原本是linle 的，现在就准备送给你了。不过，任何事情都没有那么简单，你必须首先告诉我这块地到底有多少面积，如果回答正确才能真正得到这块地。
发愁了吧？就是要让你知道，种地也是需要AC知识的！以后还是好好练吧...

 

Input

输入数据包含多个测试实例，每个测试实例占一行，每行的开始是一个整数n(3<=n<=100)，它表示多边形的边数（当然也是顶点数），然后是按照逆时针顺序给出的n个顶点的坐标（x1, y1, x2, y2... xn, yn）,为了简化问题，这里的所有坐标都用整数表示。
输入数据中所有的整数都在32位整数范围内，n=0表示数据的结束，不做处理。

 

Output

对于每个测试实例，请输出对应的多边形面积，结果精确到小数点后一位小数。
每个实例的输出占一行。

 

Sample Input

3 0 0 1 0 0 1 4 1 0 0 1 -1 0 0 -1 0

 

Sample Output

0.5 2.0

最终AC代码如下：

#include <cstdio>
typedef struct point{
    int x, y;
};
double getArea(point a, point b){
    return a.x*b.y - a.y*b.x; //此处为什么不需要绝对值？？？ 
}
int main(){
    int i, n;
    point p[101];
    double ans;
    while(scanf("%d", &n) && n) {
        for(i=0; i<n; i++){
            scanf("%d %d", &(p[i]).x, &(p[i]).y);
            if(i > 0){
                p[i].x -= p[0].x; //以p[0]为公共点 
                p[i].y -= p[0].y;
            }
        }
        ans = 0;
        for(i=1; i<n-1; i++) ans += getArea(p[i], p[i+1]);
        printf("%.1lf
", ans/2);
    }
    return 0;
}

主要参考资料：

1、HDU 2036 改革春风吹满地

2、利用向量积（叉积）计算三角形的面积和多边形的面积

总结：用向量叉积的形式求面积，我倒真的没想过，第一反应就是采用海伦公式解，但是通不过。不知道是不是测试用例的问题~另一个疑惑点是，向量叉积是有正负的，虽然顶点是按逆时针方向排列的，返回值一定是正的，但是为什么我返回前加上fabs()函数后，在OJ上反而不能通过了呢？这个问题目前没有想明白，写下来先记录吧。

关于用海伦的写法如下：（不知道是算法本身存在问题，还是所采用的测试用例不能用海伦来解？）

#include <bits/stdc++.h> 
using namespace std;
typedef long long int LL;

//用海伦公式不能通过！ 
//由三边 求三角形面积 => 海伦公式 
//p = (a+b+c)/2;
//S = sqrt(p*(p-a)*(p-b)*(p-c)); 

int main(){
    double p, t1, t2, t3, ans;
    LL i, n, a, b;
    vector<double> vd;
    vector<pair<LL, LL> > vp;
    while(scanf("%lld", &n), n!=0){
        vp.clear();
        for(i=0; i<n; i++){
            scanf("%lld %lld", &a, &b);
            vp.push_back(make_pair(a, b));
        }
        vd.clear();
        for(i=0; i<n; i++){
            a = (vp[(i+1)%n]).first - (vp[i]).first;
            b = (vp[(i+1)%n]).second - (vp[i]).second;
            vd.push_back(sqrt(1.0*(a*a+b*b)));
        }
        ans = 0;
        t1 = vd[0];
        for(i=2; i<vd.size(); i++){
            t2 = vd[i-1];
            a = (vp[0]).first - (vp[i]).first;
            b = (vp[0]).second - (vp[i]).second;
            t3 = sqrt(1.0 * (a*a + b*b));
            p = (t1 + t2 + t3) / 2;
            ans += sqrt(p * (p-t1) * (p-t2) * (p-t3));
            t1 = t3;
        }
        printf("%.1lf
", ans);
    }
    return 0;
}