多邊形重心問題
時間限制：3000 ms? |? 內(nèi)存限制：65535 KB
難度：5
描述 在某個多邊形上，取n個點(diǎn)匾旭，這n個點(diǎn)順序給出镣屹，按照給出順序?qū)⑾噜彽狞c(diǎn)用直線連接， （第一個和最后一個連接）价涝，所有線段不和其他線段相交女蜈，但是可以重合，可得到一個多邊形或一條線段或一個多邊形和一個線段的連接后的圖形；
如果是一條線段,我們定義面積為0伪窖，重心坐標(biāo)為（0,0）.現(xiàn)在求給出的點(diǎn)集組成的圖形的面積和重心橫縱坐標(biāo)的和逸寓；
輸入第一行有一個整數(shù)0<n<11,表示有n組數(shù)據(jù)；
每組數(shù)據(jù)第一行有一個整數(shù)m<10000,表示有這個多邊形有m個頂點(diǎn)覆山；輸出輸出每個多邊形的面積竹伸、重心橫縱坐標(biāo)的和，小數(shù)點(diǎn)后保留三位簇宽；樣例輸入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
#include<iostream>
#include<cmath>
using namespace std;
#define INF 0.0000001
int main()
{
int n,m;
int i;
double x[10010],y[10010];
double sum,dots;
cin>>m;
while(m--)
{
//賦初值
dots = sum = 0;
//輸入數(shù)據(jù)
cin>>n;
for(i=0; i<n; i++)
{
cin>>x[i]>>y[i];
}
//計(jì)算
for(i=1; i<=n; i++)
{
//本題重點(diǎn)
//分割成若干三角形求
double temp = (y[i-1]*x[i%n] - y[i%n]*x[i-1]) / 2.0;//臨時面積
sum += temp;
//物理知識求重心（貌似是高數(shù)里的）
dots += temp * (x[i%n] + x[i-1] + y[i%n] + y[i-1]) / 3.0;
}
cout.precision(3);
if(sum < INF)//如果改為sum == 0 會增加時間的消耗
{
cout<< "0.000" <<' '<< "0.000" <<endl;
}
else
{
cout<<fixed<< fabs(sum) <<' '<< dots/sum <<endl;
}
}
return 0;
}
#include <stdio.h>
#include <math.h>
inline double g(double x1,double y1,double x2,double y2,double x3,double y3)
{?
? ? return (x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2)/2;
}
int main()
{?
? ? int n,m;? scanf("%i",&n);?
while(n--){?
scanf("%i",&m);?
m-=2;?
double x1,y1,x,y,xn,yn,gsx=0,gsy=0,s=0,cs=0;?
scanf("%lf%lf%lf%lf",&x1,&y1,&x,&y);?
while(m--)? {? ?
? scanf("%lf%lf",&xn,&yn);? ?
? s+=(cs=g(x1,y1,x,y,xn,yn));? ?
? gsx+=(x1+x+xn)*cs/3;? ?
? gsy+=(y1+y+yn)*cs/3;? ?
? x=xn;? ?
? y=yn;?
}?
printf("%.3f %.3f\n",fabsf(s),(s==0?0.0:fabsf((gsx+gsy)/s)));?
}
}
