Beyond the Void
BYVoid
USACO 5.1.1 Fencing the Cows 圈奶牛 fc

这道题是一道最基本的求凸包的题。如果不熟悉求凸包的算法,可以正好通过这道题来入门。我学的是格拉汉扫描法(Graham扫描法)。这种算法直观而且简单,推荐使用。

格拉汉扫描法基本过程:

从一个必定在凸包边上的顶点为起始点开始寻找凸包(例如最右边的点)

把其他所有点按到起始点的辐角大小顺序排序

将起始点和第一个点压入堆栈

for i=2 to N 从第二个点一直到最后一个点

{

将当前顶点加入堆栈

判断是否形成凹角(大于180度)
计算叉积 fp=stack[TOP-1]->stack[TOP],stack[TOP-1]->stack[TOP-2]

若fp<0,不通过判断
stack[TOP-1]=stack[TOP]
TOP--
重新判断,直到找到凸角

}

USER: CmYkRgB123 CmYkRgB123 [cmykrgb1]
TASK: fc
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 3036 KB]
   Test 2: TEST OK [0.000 secs, 3040 KB]
   Test 3: TEST OK [0.000 secs, 3036 KB]
   Test 4: TEST OK [0.000 secs, 3040 KB]
   Test 5: TEST OK [0.011 secs, 3036 KB]
   Test 6: TEST OK [0.032 secs, 3036 KB]
   Test 7: TEST OK [0.032 secs, 3036 KB]
   Test 8: TEST OK [0.065 secs, 3036 KB]

All tests OK.

Your program ('fc') produced all correct answers!  This is your
submission #2 for this problem.  Congratulations!

/*
ID: cmykrgb1
PROG: fc
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#define MAXN 10001
#define INF 0x7FFFFFFF
using namespace std;
typedef struct
{
	double x,y;
} TPoint;
ifstream fi("fc.in");
FILE *fo;
int N,top;
TPoint P[MAXN],ST,Z,*stack[MAXN];

double FP(TPoint &l1s,TPoint &l1e,TPoint &l2s,TPoint &l2e)
{
	TPoint l1,l2;
	l1.x=l1e.x-l1s.x;l1.y=l1e.y-l1s.y;
	l2.x=l2e.x-l2s.x;l2.y=l2e.y-l2s.y;
	return l1.x*l2.y-l2.x*l1.y;
}

double dis(double x1,double y1,double x2,double y2)
{
	return sqrt( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) );
}

int cmp(const void *A,const void *B) //把除了ST点外的所有点,旋转角度排序 
{
	TPoint *a=(TPoint *)A; TPoint *b=(TPoint *)B; 
	double fp=FP(*a,ST,*b,ST);
	if( fp < 0) return 1;
	if( fp == 0 && dis(a->x,a->y,ST.x,ST.y) < dis(b->x,b->y,ST.x,ST.y)) // 如果在一条直线上,则把远的放在前面
		return 1;
	return -1;
}

void init()
{
	int i,st;
	double maxx=-INF;
	fi >> N;
	for (i=1;i<=N;i++)
	{
		fi >> P[i].x >> P[i].y;
		if (P[i].x>maxx)
		{
			maxx=P[i].x;
			ST=P[i];
			st=i;
		}
	}
	P[st]=P[N];	P[N--]=Z;
	qsort(P+1,N,sizeof(TPoint),cmp);
}

void graham()
{
	int i;
	double fp;
	stack[0]=&ST;
	stack[top=1]=&P[1];
	for (i=2;i<=N;i++)
	{
		stack[++top]=&P[i];
		fp=FP(*stack[top-1],*stack[top],*stack[top-1],*stack[top-2]);
		while (fp<0)
		{
			stack[top-1]=stack[top];
			top--;
			fp=FP(*stack[top-1],*stack[top],*stack[top-1],*stack[top-2]);
		}
	}
}

void print()
{
	int i;
	double ans=0;
	for (i=1;i<=top;i++)
		ans+=dis(stack[i-1]->x,stack[i-1]->y,stack[i]->x,stack[i]->y);
	ans+=dis(stack[top]->x,stack[top]->y,stack[0]->x,stack[0]->y);
	fi.close();
	fo=fopen("fc.out","w");
	fprintf(fo,"%.2lfn",ans);
	fclose(fo);
}

int main()
{
	init();
	graham();
	print();
	return 0;
}

上次修改时间 2017-05-22

相关日志