hdu Surround the Trees

题目链接：戳我

凸包模板
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define MAXN 100010

using namespace std;

int n,top;

double ans;

struct Node{int x,y;}t[MAXN],s[MAXN];

inline bool cmp(struct Node a,struct Node b)

{

	double A=atan2((a.y-t[1].y),(a.x-t[1].x));

	double B=atan2((b.y-t[1].y),(b.x-t[1].x));

	if(A!=B) return A<B;

	else return a.x<b.x;

}

inline double cross(Node a,Node b,Node c){return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);}

inline void solve()

{

	t[0]=(Node){0x3f3f3f3f,0x3f3f3f3f};

	int k=0;

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

		if(t[i].y<t[0].y||(t[i].y==t[0].y&&t[i].x<t[0].x))

			t[0]=t[i],k=i;

	swap(t[1],t[k]);

	sort(&t[2],&t[1+n],cmp);

	s[0]=t[1],s[1]=t[2];

	top=1;

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

	{

		while(top&&cross(s[top-1],t[i],s[top])>=0.0) top--;

		s[++top]=t[i];

	}

}

int main()

{

	#ifndef ONLINE_JUDGE

	freopen("ce.in","r",stdin);

	#endif

	for(;;)

	{

		ans=0.0;

		scanf("%d",&n);

		if(!n) break;

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

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

		solve();

		if(top==0)

			ans=0;

		else if(top==1)

			ans=sqrt((s[0].x-s[1].x)*(s[0].x-s[1].x)+(s[0].y-s[1].y)*(s[0].y-s[1].y));

		else

		{

			s[++top]=s[0];

			for(int i=0;i<top;i++)

			{

				Node a=s[i],b=s[i+1];

				ans+=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

			}

		}

		printf("%.2lf\n",ans);

	}

	return 0;

}
巴特西

hdu Surround the Trees

题目链接：戳我

最新文章

热门文章
