題意：

給出一個n邊形，我們要輸出有多少種擺放方案使得這個多邊形能夠穩定擺放（如果重心落在邊的端點上，不能穩固）。

思路：

用這n個點圍成一個凸包，每次用凸包的一個邊當做底邊，判斷重心是否落在這條邊的端點上或者落在邊的外面即可。

注意：一定要用初始的n邊形求重心，不能用凸包求重心，因為這個我們WA了三個小時。

代碼：

#include <cstdio> #include <cstring> #include <cmath> #include <queue> #include <iostream> #include <algorithm> using namespace std; const int maxn=500005*2; //const double pi=atan(1.0)*4; const double eps = 1e-8; int cmp(double x) {if(fabs(x) < eps) return 0;if(x > 0) return 1;return -1; } struct node{double x,y; }e[maxn],res[maxn]; int cmp1(node a,node b) {if(cmp(a.x-b.x) == 0) return cmp(a.y-b.y) < 0;return cmp(a.x-b.x)<0; } double cross(node a,node b,node c)//向量積 {return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y); } int convex(int n)//求凸包上的點 {sort(e,e+n,cmp1);int m=0,i,j,k;for(i=0;i<n;i++){while(m>1&&cmp(cross(res[m-1],e[i],res[m-2]))<=0)m--;res[m++]=e[i];}k=m;for(i=n-2;i>=0;i--){while(m>k&&cmp(cross(res[m-1],e[i],res[m-2]))<=0)m--;res[m++]=e[i];}if(n>1)m--;return m; }struct point {double x, y;point() {};point(double a, double b) : x(a), y(b) {};friend point operator + (const point & a, const point &b) {return point(a.x + b.x , a.y + b.y );}friend point operator - (const point & a, const point &b) {return point(a.x - b.x, a.y - b.y);}friend point operator * (const point & a, const double &b) {return point(a.x * b, a.y * b);}friend point operator / (const point & a, const double &b) {return point(a.x / (b+eps), a.y / (b + eps));} };double det(const point &a,const point &b) {return a.x * b.y - a.y * b.x; }struct polygon {int n;point a[maxn];polygon() {};double area() { // printf("nnnnnnnnnnnnnnnnnnnnnnnn%d\n", n);double sum = 0;a[n] = a[0];for(int i = 0; i < n; i++) { // puts("JJJJJ");sum += det(a[i + 1], a[i]);}return sum / 2;}point center() {point ans = point(0, 0); // printf("a = %lf\n",area());if(cmp(area()) == 0) return ans;a[n] = a[0];for(int i = 0; i < n; i++) {ans = ans +(a[i] + a[i + 1]) * det(a[i + 1], a[i]);}return ans / area() / 6.0;} };polygon p1; polygon p2; double dot(point a, point b) {return a.x * b.x + a.y * b.y; } void PointPro(point p,point s,point t,point &cp) {double r = dot((t - s),(p - s))/dot(t-s,t - s);cp = s + (( t - s) * r); }bool On(point p, point s, point t) {if(cmp(p.x - s.x) == 0 && cmp(p.y - s.y) == 0) return false;if(cmp(p.x - t.x) == 0 && cmp(p.y - t.y) == 0) return false;return cmp(det(p-s, t - s)) == 0&& cmp(dot(p-s,p-t))<=0; }int main() { // freopen("a.txt","r",stdin);int T,n,l;scanf("%d",&T);while(T--){scanf("%d",&n);for(int i = 0; i < n; i++){cin >> e[i].x >> e[i].y; // e[i].x *= 1000; // e[i].y *= 1000;p2.a[i]=point(e[i].x*1.0,e[i].y*1.0);}p2.n=n;point p0 = p2.center();int m=0;m=convex(n); // if(m == 2) { // if(cmp(res[0].x - res[1].x) == 0 && cmp(res[0].y - res[1].y) == 0 ) { // printf("0\n"); // continue; // } // else{ // printf("2\n"); // continue; // } // }int _ans = 0;p1.n = m; // printf("p1.n = %d\n", p1.n);for(int i = 0; i < m; i++) {p1.a[i] = point(res[i].x * 1.0 , res[i].y * 1.0 );} // for(int i = 0; i < m; i++) { // printf("%lf %lf\n", p1.a[i].x , p1.a[i].y ); // } // printf("p1.n = %d\n", p1.n);// printf("%lf %lf\n", p0.x, p0.y);for(int i = 0; i < m; i++){point jiaodian;PointPro(p0, p1.a[i], p1.a[(i + 1) % m], jiaodian);if(On(jiaodian, p1.a[i], p1.a[(i+1)%m])) {_ans++;} // printf("jiaod = %lf %lf %d\n", jiaodian.x, jiaodian.y,_ans);}printf("%d\n", _ans);}return 0; }

總結

以上是生活随笔為你收集整理的uvalive4838(凸包+重心)的全部內容，希望文章能夠幫你解決所遇到的問題。

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