hdu3685（几何重心与凸包结合）

题意：给一个多边形（有可能是凹多边形）。问有多少种可以使得它稳定放置的方式。当然稳定的原则就是重心做垂线在支撑点之内。

解法：由于有可能是凹多边形，所以先求出多边形的凸包，这是在放置时候会接触地面的全部点。

然后将重心与每天凸边推断是否稳定。

代码：

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string.h>
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps 1e-8
#define zero(_) (_<=eps)
const double pi=acos(-1.0);
typedef long long LL;
const int Max=100010;
const LL INF=0x3FFFFFFF;
struct point
{
    double x,y;
};
point points[50005];
point focus;
int top;
int stack[50005];
int N;
double mult(point a,point b,point c)
{
    a.x-=c.x;
    a.y-=c.y;
    b.x-=c.x;
    b.y-=c.y;
    return a.x*b.y-a.y*b.x;
}

double dis(const point& a,const point& b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

bool operator<(point a,point b)
{
    if(mult(a,b,points[0])>0||(mult(a,b,points[0])==0 && a.x<b.x))
        return true;
    else
        return false;
}
point OK(point a,point b,point c)
{
    point ans;
    ans.x=(a.x+b.x+c.x)/3;
    ans.y=(a.y+b.y+c.y)/3;
    return ans;
}
void getFocus(point& focus,point* points,int N)
{
    focus.x=0;
    focus.y=0;
    double base=0;
    for(int i=2; i<N; i++)
    {
        double t=mult(points[0],points[i-1],points[i]);
        point pp=OK(points[0],points[i-1],points[i]);
        focus.x+=t*pp.x;
        focus.y+=t*pp.y;
        base+=t;
    }
    focus.x/=base;
    focus.y/=base;
}
int getans()
{
    int ans=0;
    for(int i=0; i<top; i++)
    {
        double l=dis(focus,points[stack[i]]);
        double r=dis(focus,points[stack[i+1]]);
        double u=dis(points[stack[i]],points[stack[i+1]]);
        if(l+u>r&&r+u>l)
            ans++;
    }
    double l=dis(focus,points[stack[top]]);
    double r=dis(focus,points[stack[0]]);
    double u=dis(points[stack[top]],points[stack[0]]);
    if(l+u>r&&r+u>l)
        ans++;
    return ans;
}
void graham(int n)
{
    int mi=0;
    for(int i=1; i<n; i++)
    {
        if(points[i].y<points[mi].y||(points[i].y==points[mi].y&&points[i].x<points[mi].x))
            mi=i;
    }
    point a=points[0];
    points[0]=points[mi];
    points[mi]=a;
    sort(points+1,points+n);
    stack[0]=0;
    stack[1]=1;
    stack[2]=2;
    top=2;
    for(int i=3; i<n; i++)
    {
        while(top>0&&mult(points[stack[top]],points[stack[top-1]],points[i])>=0)
        {
            top--;
        }
        stack[++top]=i;
    }
}


int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        scanf("%d",&N);
        for(int i=0; i<N; i++)
        {
            scanf("%lf%lf",&points[i].x,&points[i].y);
        }
        getFocus();
        graham(N);
        cout<<getans()<<endl;
    }
    return 0;
}