二叉查找

多边形重心问题 java

看题目 点这里
题目描述：
描述
在某个多边形上，取n个点，这n个点顺序给出，按照给出顺序将相邻的点用直线连接， （第一个和最后一个连接），所有线段不和其他线段相交，但是可以重合，可得到一个多边形或一条线段或一个多边形和一个线段的连接后的图形；
如果是一条线段,我们定义面积为0，重心坐标为（0,0）.现在求给出的点集组成的图形的面积和重心横纵坐标的和；

输入
第一行有一个整数0<n<11,表示有n组数据；
每组数据第一行有一个整数m<10000,表示有这个多边形有m个顶点；
输出
输出每个多边形的面积、重心横纵坐标的和，小数点后保留三位；
样例输入

3
3
0 1
0 2
0 3
3
1 1
0 0
0 1
4
1 1
0 0
0 0.5
0 1

样例输出

0.000 0.000
0.500 1.000
0.500 1.000

本题的解题思路：
1.多边形面积怎么求。

将多边形分割成多个三角形即可对三角形面积求和

2.三角形面积用叉积怎么求 。

x2*y1-x1y2 详细描述 点这里 当然大家也可以自己去谷歌
3 求重心坐标关系。

把多边形的每个三角形看作一个质量为面积的点，然后将每个点的横坐标和这个三角形的面积相乘后结果相加。最终结果除以多边形面积就是多边形重心的X坐标。Y同理求得。

具体代码如下：

import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        int n=0;
        Scanner s=new Scanner(System.in);
        n=s.nextInt();
        for(int i=0;i<n;i++){
            int n1=s.nextInt();
            double data[][]=new double[n1][2];
            double sc=0;
            double sx=0;
            double sy=0;
            for(int j=0;j<n1;j++){
                data[j][0]=s.nextDouble();
                data[j][1]=s.nextDouble();
            }           
             for (int j = 1; j <= n1; j++) {  
                    double temp=(data[j % n1][0]*data[j-1][1]-data[j % n1][1]*data[j -1][0])/2.0;  
                    sc=sc+temp;
                    sx=sx+temp*(data[j % n1][0]+data[j-1][0])/3;
                    sy=sy+temp*(data[j % n1][1]+data[j-1][1])/3;
                }  
        
          //result取绝对值  
             if (sc - 0 < 0.0000001) {  
                    System.out.println("0.000 0.000");  
                    continue;  
                }  
                    System.out.print(String.format("%.3f %.3f\n",sc,(sx + sy)/sc));  
                
        }
        
    }
}