USACO 5.1.1 Fencing the Cows 圈奶牛 fc
本文正體字版由OpenCC轉換
這道題是一道最基本的求凸包的題。如果不熟悉求凸包的算法，可以正好通過這道題來入門。我學的是格拉漢掃描法(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