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;
}

相關日誌