NYOJ3(多邊形重心)

NYOJ3(多邊形重心)

如果是一條線段,我們定義面積為0，重心坐標為（0,0）.現在求給出的點集組成的圖形的面積和重心橫縱坐標的和。

輸入第一行有一個整數0 每組數據第一行有一個整數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

題目分析：

此題是一個多邊形重心問題，直接上模板進行了，只是不知道為什麼將多邊形分成在n個點中任選一個點分成n-2個三角形求解問什麼過不了，最後以原點為中心進行劃分反而過了？下面貼上AC代碼。

 

AC代碼：

/**
*①質量集中在頂點上
* n個頂點坐標為(xi,yi)，質量為mi，則重心
*　X = ∑( xi×mi ) / ∑mi
*　Y = ∑( yi×mi ) / ∑mi
*　特殊地，若每個點的質量相同，則
*　X = ∑xi / n
*　Y = ∑yi / n
*②質量分布均勻
*　特殊地，質量均勻的三角形重心：
*　X = ( x0 + x1 + x2 ) / 3
*　Y = ( y0 + y1 + y2 ) / 3
*③三角形面積公式：S = ( (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) ) / 2 ;
*做題步驟：1、將多邊形分割成n-2個三角形，根據③公式求每個三角形面積。
* 2、根據②求每個三角形重心。
* 3、根據①求得多邊形重心。
**/
#include
#include
#include
using namespace std;
struct Point{
double x,y;
}p[10005];
double Area(Point p1,Point p2,Point p3){//叉乘求三角形面積
return ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))/2.0;
}
int main()
{
int n,t;
Point p0;
p0.x=p0.y=0.0;
scanf(%d,&t);
while(t--){
scanf(%d,&n);
double gx,gy,sumarea,area;
gx=gy=sumarea=0;
for(int i = 0; i < n; ++i)
scanf(%lf%lf, &p[i].x, &p[i].y);
for(int i=1;i<=n;i++){
area=Area(p0,p[i%n],p[i-1]);//與原點單個三角的面積
gx+=(p[i%n].x+p[i-1].x)*area;//重心乘以其權值(面積),因為每一個都要除以3,所醫院放在最後
gy+=(p[i%n].y+p[i-1].y)*area;
sumarea+=area;//計算所有權值
}

if(sumarea < 0.0000001 && sumarea >-0.0000001){
printf(0.000 0.000 );
continue;
}
/**
gx=gx/(sumarea*3);//求的多邊形重心
gy=gy/(sumarea*3);
**/
printf(%.3lf %.3lf ,sumarea,(gx+gy)/(sumarea*3));
//printf(%.2lf %.2lf ,gx,gy);
}
return 0;
}