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