Lifting the Stone

http://acm.hdu.edu.cn/showproblem.php?pid=1115

題目描述：輸入n個頂點（整數）,求它們圍成的多邊形的重心。

算法：以一個點出發，與其他非鄰點相連，將n邊形劃分成n-2個三角形。求每個三角形的質點系重心（如：((x1+x2+x3)/3,(y1+y2+y3)/3)），再求出每個三角形的面積。相乘求和后除以多邊形面積）。

注意：we connect the points in the given order。輸入的順序，要么是順時針，要么是逆時針。

#include <iostream> #include <iomanip> #include <vector> using namespace std; struct Node //頂點或向量結構 {int x;int y; }; vector<Node> node; int main() {int t,n;double cross_sum,x_sum,y_sum;cin>>t;while(t--){node.clear();cross_sum=0;x_sum=y_sum=0;cin>>n;for(int i=1;i<=n;i++){Node temp; //頂點cin>>temp.x>>temp.y;node.push_back(temp);}Node vec1,vec2; //向量vec1.x=node[1].x-node[0].x;vec1.y=node[1].y-node[0].y;for(int i=2;i<=n-1;i++){vec2.x=node[i].x-node[0].x;vec2.y=node[i].y-node[0].y;int cross=vec1.x*vec2.y-vec2.x*vec1.y;x_sum+=(double)(node[0].x+node[i-1].x+node[i].x)*cross;y_sum+=(double)(node[0].y+node[i-1].y+node[i].y)*cross;cross_sum+=cross;vec1=vec2;}double res_x=x_sum/(3*cross_sum);double res_y=y_sum/(3*cross_sum); //最后用除法，且少用除法，減少精度丟失cout<<fixed<<setprecision(2)<<res_x<<" "<<res_y<<endl;}return 0; } View Code

做了幾道計算幾何的題目，不得不說向量是個好東西！！！是哪位神人發明的向量，膜拜。

?

下面是別人寫的的求多邊形重心的方法：

線垂法：

　　具體方法是：用細線提起該物體，在該物體上畫細線的延長線，再移位用細線提起該物體，在該物體上畫細線的延長線，兩線的交叉點就是這一物體在這平面上的重心，　　　　　　　　其它面同理．適用于實際測量中。

?

定理法：(本人自己命名)
　　定理1： 由兩個圖形A，B合并而成的一個圖形C，則C的重心必在A的重心與B的重心連接的線段上。(注意，也適用于A B彼此分開，沒有公共點的情形)
　　定理2： 由兩個A，B合并而成的一個圖形C，A的重心為點a, B的重心為點b, C的重心為點c, A的面積為Sa, B的面積為Sb,則下面條件成立：
　　　　　　(1)點c 必在線段 ab 上
　　　　　　(2) ac * Sa = bc * Sb

計算幾何中：
　　　　三角形的重心： x = (xa+xb+xc)/3, ?y = (ya+yb+yc)/3;
　　　　四邊形的重心：作一對角線，將它分成兩個三角形分別求出重心與面積 (x1,y1) ,s1 ; (x2, y2), s2 則該四邊形的重心為： x = (x1*s1+x2*s2)/(s1+s2), y = (y1*s1+y2*s2)/(s1+s2);
　　　　五邊形則分為一個三角形與一個四邊形……

　　　　任意多邊形中直接取任一點（一般為原點）把多邊形分為n-2個三角形 分別求重心
　　　　　　x=∑ si * xi / ∑si
　　　　　　y=∑ si * yi / ∑si
　　　　　　si 為每塊三角形的有向面積?(就是向量叉積/2)

轉載于:https://www.cnblogs.com/chiry/p/3505949.html

總結

以上是生活随笔為你收集整理的HDOJ（1115）多边形重心的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。