PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

ACM 10002 Center of Masses

看板Prob_Solve (計算數學 Problem Solving)作者Jett (Jett)時間23年前 (2001/09/05 08:26)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串1/2 (看更多)

有人寫過這一題嗎？有什麼陷阱嗎？這題是找 convex polygon 的質心我用的方法是先做一次 Graham Scan 然後 v0v1v2, v0v2v3, v0v3v4, ..., v0vn-1vn 對每一個三角形，計算其面積，再加權至它的重心最後 sum 起來再 Normalize 總面積即得此 convex polygon 的質心不過 WA 了好幾次，不曉得是不是還有其他的陷阱？謝謝各位。 -- 另，附我的程式碼如下： -- #include <stdio.h> #include <stdlib.h> #include <math.h> #define STDIN stdin #define MAX_V 102 /* 定義點的資料型態 */ typedef struct { int x,y; } t_point; /* 定義線的資料型態 */ typedef struct { t_point p1,p2; } t_line; /* 定義多邊形的資料型態 */ typedef struct { int n; t_point p[MAX_V]; } t_poly; t_point start_point; /* 檢查從p0到p1至p2是 counterclockwise(1) or clockwise(-1) */ int ccw(t_point p0, t_point p1, t_point p2) { return ( (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y) ); } /* 依逆時針方向將點排序 */ int sort_by_theta( const void *a, const void *b ) { int dx1,dy1,d1,adxy1,dx2,dy2,d2,adxy2; t_point p0,p1,p2; p0 = start_point; p1 = *(t_point *)a; p2 = *(t_point *)b; dx1=p1.x-p0.x; dy1=p1.y-p0.y; adxy1=abs(dx1)+abs(dy1); d1=dy1; dx2=p2.x-p0.x; dy2=p2.y-p0.y; adxy2=abs(dx2)+abs(dy2); d2=dy2; if (dx1<0) d1=2*adxy1-dy1; else if (dy1<0) d1=4*adxy1+dy1; if (dx2<0) d2=2*adxy2-dy2; else if (dy2<0) d2=4*adxy2+dy2; return (d1*adxy2-d2*adxy1); } /* Graham Scan */ int graham_scan(t_point p[], int n) { int i, M, min; t_point temp; for (min=0, i=1; i<n; i++) if (p[i].y < p[min].y) min=i; for (i=0; i<n; i++) if ( p[i].y == p[min].y && p[i].x < p[min].x ) min = i; temp = p[0]; p[0] = p[min]; p[min] = temp; start_point = p[0]; qsort((void *)&p[1], n-1, sizeof(t_point), sort_by_theta); for (M=2, i=3; i<n; i++) { while ( M > 0 ) { if (ccw(p[M-1],p[M],p[i])<=0) M--; else break; } M++; temp = p[M]; p[M] = p[i]; p[i] = temp; } return M+1; } /* 傳回某一多邊形之面積，除以 2.0 不做，因為最後會 Normalize 掉 */ double area(t_poly poly) { int i,A=0; poly.p[poly.n] = poly.p[0]; for (i=1;i<=poly.n;i++) A += poly.p[i-1].x*poly.p[i].y - poly.p[i].x*poly.p[i-1].y; return (double)A; } /* 計算某三角形之重心，除以 3.0 挪至 cal_center 再做 */ void cal_tri_center( t_poly pl, double *center_x, double *center_y ) { *center_x = ((double)(pl.p[0].x + pl.p[1].x + pl.p[2].x)); *center_y = ((double)(pl.p[0].y + pl.p[1].y + pl.p[2].y)); } /* 計算某多邊形之重心 */ void cal_center( t_poly pl, double *center_x, double *center_y ) { int i; double x, y, t_x, t_y, tri_area, total_area; t_poly tri_poly; x = y = total_area = 0.0; tri_poly.n = 3; tri_poly.p[0] = pl.p[0]; for(i=1; i<=pl.n-2; i++) { tri_poly.p[1] = pl.p[i]; tri_poly.p[2] = pl.p[i+1]; cal_tri_center( tri_poly, &t_x, &t_y); tri_area = area(tri_poly); x += tri_area*t_x; y += tri_area*t_y; total_area += tri_area; } *center_x = x / (total_area*(double)3.0); *center_y = y / (total_area*(double)3.0); } int main(void) { int i; t_poly poly; double center_x, center_y; while ( fscanf(STDIN,"%d",&(poly.n)) != EOF ) { if (poly.n < 3) break; for(i=0; i<poly.n; i++) fscanf(STDIN, "%d%d", &(poly.p[i].x), &(poly.p[i].y)); poly.n = graham_scan(poly.p, poly.n); cal_center(poly, &center_x, &center_y); printf("%.3lf %.3lf\n", center_x, center_y); } } -- ※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw) ◆ From: 211.74.25.112