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;

}