POJ 3348 Cows | 凸包模板题

题目:

给几个点,用绳子圈出最大的面积养牛,输出最大面积/50

题解:

Graham凸包算法的模板题

下面给出做法

1.选出x坐标最小(相同情况y最小)的点作为极点(显然他一定在凸包上)

2.其他点进行极角排序<极角指从坐标轴的某一方向逆时针旋转到向量的角度>,

　极角一样按距离从近到远(可以用叉积实现)

3.用栈维护凸包上的点,将极点和极角序最小的点依次入栈

4.按顺序扫描,检查栈顶的前两个元素与这个点构成的线段是否拐向右(顺时针侧,叉积小于0)

　如果满足就弹出栈顶元素,直到不满足或者栈里不足两个元素

　反之入栈

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<stack>

#define N 10005

using namespace std;

int n,m;

struct point

{

    int x,y;

    point (){};

    point (int _x,int _y)

	{

	    x=_x,y=_y;

	}

    point operator - (const point &a)const

	{

	    return point (x-a.x,y-a.y);

	}

    int operator * (const point &a) const

	{

	    return x*a.y-y*a.x;

	}

    int norm()const

	{

	    return x*x+y*y;

	}

}p[N],q[N];

bool cmp(int u,int v)

{

    int det=(p[u]-p[1])*(p[v]-p[1]);

    if (det!=0) return det>0;

    return (p[u]-p[1]).norm() < (p[v]-p[1]).norm();

}

void Graham()

{

    int id=1;

    for (int i=2;i<=n;i++)

	if (p[i].x<p[id].x || (p[i].x==p[id].x && p[i].y<p[id].y))

	    id=i;

    if (id!=1) swap(p[1],p[id]);

    int per[N];

    for (int i=1;i<=n;i++)

	per[i]=i;

    sort(per+2,per+1+n,cmp);

    q[++m]=p[1];

    for (int i=2;i<=n;i++)

    {

	int j=per[i];

	while (m>=2 && (p[j]-q[m-1])*(q[m]-q[m-1])>=0) m--;

	q[++m]=p[j];

    }

}

int Area()

{

    int res=0;

    q[m+1]=q[1];

    for (int i=1;i<=m;i++)

	res+=q[i]*q[i+1];

    return res/2;

}

int main()

{

    scanf("%d",&n);

    for (int i=1;i<=n;i++)

	scanf("%d%d",&p[i].x,&p[i].y);

    Graham();

    int ans=Area()/50;

    printf("%d\n",ans);

    return 0;

}

巴特西

POJ 3348 Cows | 凸包模板题

最新文章

热门文章