程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu3685（幾何重心與凸包結合）

hdu3685（幾何重心與凸包結合）

編輯：C++入門知識

hdu3685（幾何重心與凸包結合）

題意：給一個多邊形（有可能是凹多邊形）。問有多少種能夠使得它穩定放置的方式。當然穩定的原則就是重心做垂線在支撐點之內。

解法：因為有可能是凹多邊形，所以先求出多邊形的凸包，這是在放置時候會接觸地面的所有點。然後將重心與每天凸邊判斷是否穩定；

代碼：

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//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.xr&&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; i0&&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