杭电OJ-ACM2036（改革春风吹满地）-创新互联

题目分析：原题给出的条件是通过多组数据的各个坐标（用逆时针表达）求出对应的“任意”多边形的面积大小.

创新互联长期为千余家客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为东洲企业提供专业的成都网站建设、做网站，东洲网站改版等技术服务。拥有十余年丰富建站经验和众多成功案例,为您定制开发。

法一（Time Limit Exceeded（×）【Java版】）：

主要思路——

对一个多边形进行拆解，若含有n条边，（记其坐标分别为（X0，Y0），（X1，Y1），（X2，Y2），......，（Xn-1，Yn-1）），则我们可以以（X0，Y0）为原点，将其分为n-2个三角形。如下如所示.

因其可见，当我们以（X0，Y0）为n-2个小三角的公共点时，每个小三角形的另外两边都是从（X1，Y1）到（Xn-1，Yn-1）的相邻两边!我们需要求出每个小三角的面积大小。首先，我们使用static静态方法进行每个小三角求面积的方法定义；在此，我们输入三个端点坐标后，通过坐标可求得三边的边长并由此我们依“海伦公式”便可解得答案.（若三角形的三边分别为a，b，c，令p=（a+b+c）/2，则面积S=√p（p-a）（p-b）（p-c））.

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner kc = new Scanner(System.in);
        while (kc.hasNextDouble()) {
            int n = kc.nextInt();
            double area=0;
            if (n != 0) {
                int[] x = new int[n];
                int[] y = new int[n];
                for (int i = 0; i< n*2; i++) {
                    if (i % 2 == 0) {
                        x[i / 2] = kc.nextInt();
                    } else {
                        y[i / 2] = kc.nextInt();
                    }
                }
                if (n == 3) {
                    area = triangleArea(x[0], y[0], x[1], y[1], x[2], y[2]);
                    System.out.println(String.format("%.1f", area));
                }
                if (n >3) {
                    for(int i=1;i<=n-2;i++){
                        area+=triangleArea(x[0],y[0],x[i],y[i],x[i+1],y[i+1]);
                    }
                    System.out.println(String.format("%.1f", area));
                }
            }
            else {
                break;
            }
        }
    }
    static double triangleArea(int x0, int y0, int x1, int y1, int x2, int y2){
        double d0 = Math.sqrt(Math.pow((double) x0 - (double) x1, 2)+Math.pow((double) y0 - (double) y1, 2));
        double d1 = Math.sqrt(Math.pow((double) x0 - (double) x2, 2)+Math.pow((double) y0 - (double) y2, 2));
        double d2 = Math.sqrt(Math.pow((double) x1 - (double) x2, 2)+Math.pow((double) y1 - (double) y2, 2));
        double p = (d0 + d1 + d2) / 2;
        double area=0;
        area= Math.sqrt(p * (p - d0) * (p - d1) * (p - d2));
        return area;
    }
}

最终因计算过程过于繁琐且计算量过大，系统判定为“运算超时（Time Limit Exceeded）”，况且通过笔者的深入思索发现，若输入坐标值所形成的三角形为凹三角形时，此方法可能因某些刁钻的角度问题而使面积求和不成立.

法二（Accept（√）【C++版】）——

通过鄙人的资料查阅知，在已知坐标的平面坐标系中，一个任意多边形的面积公式为：

其中，上述因输入问题，i应为“i=0”，n应为“n-1”，当i+1=n时，x（i+1）=x0，y（i+1）=y0.

即S=1/2*[(X0*Y1-X1*Y0)+(X1*Y2-X2*Y1)+...... +(Xk*Y（k+1）-X（k+1）*Yk)+...+(X（n-1）*y0-X0*Y（n-1）) ].

故最终代码为：

#include#includeusing namespace std;
int main(){
    int n;
    while(cin>>n){
        if(n==0)
            break;
        int x[n],y[n];
        for(int i=0;i>x[i]>>y[i];
        }
        double s=0;
        for(int i=0;i

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享文章：杭电OJ-ACM2036（改革春风吹满地）-创新互联
文章起源：http://bjjierui.cn/article/cecdch.html