学步园

题目链接：nyist 3http://acm.nyist.net/JudgeOnline/problem.php?pid=3

分析：题目虽然给了很多可能条件,但是只要如果给出的是一条直线的话作为特殊情况,重心坐标为0.000,0.000,其余的不管是多边形还是多边形和线段组成的图形,直接求解即可.而判断是不是一条线段利用叉积即可。

#include<iostream><br /> #include<cmath><br /> #include<iomanip><br /> using namespace std;<br /> const int MAX=10001;<br /> struct point<br /> { double x,y;<br /> };<br /> typedef point polygon[MAX];<br /> double multi(point p0,point p1,point p2)//计算叉积<br /> { return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);<br /> }<br /> int pand(polygon p,int n)//可以利用叉积证明任意三点共线<br /> { int flag=1;<br /> for(int i=0;i<n-2;i++)<br /> if(multi(p[i],p[i+1],p[i+2])!=0)<br /> { flag=0;break;<br /> }<br /> if(flag==0) return 0;<br /> return 1;<br /> }<br /> double polygon_area(polygon p,int n)//计算多边形的面积<br /> { double area=0.0;<br /> for(int i=1;i<=n;i++)<br /> area+=p[i-1].x*p[i%n].y-p[i%n].x*p[i-1].y;<br /> return fabs(area)/2;<br /> }<br /> point bcenter(point pnt[],int n)//计算多边形的重心<br /> { point p,s;<br /> double tp,area=0,tpx=0,tpy=0;<br /> p.x=pnt[0].x;p.y=pnt[0].y;<br /> for(int i=1;i<=n;++i)<br /> { s.x=pnt[i%n].x;<br /> s.y=pnt[i%n].y;<br /> tp=(p.x*s.y-s.x*p.y);area+=tp/2;<br /> tpx+=(p.x+s.x)*tp;tpy+=(p.y+s.y)*tp;<br /> p.x=s.x;p.y=s.y;<br /> }<br /> s.x=tpx/(6*area);<br /> s.y=tpy/(6*area);<br /> return s;<br /> }<br /> int main()<br /> { int n,m,i;<br /> point A;<br /> polygon p;<br /> cin>>n;<br /> while(n--)<br /> { cin>>m;<br /> for(i=0;i<m;i++)<br /> cin>>p[i].x>>p[i].y;<br /> if(!pand(p,m)) A=bcenter(p,m);<br /> else A.x=0,A.y=0;<br /> cout<<setiosflags(ios::fixed)<<setprecision(3)<<polygon_area(p,m)<<" "<<A.x+A.y<<endl;<br /> }<br /> return 0;<br /> } </p> <p>