凸包入门题目, 我用的是O(nlgn)的graham算法, 该算法的原理可以参照算法导论相关章节

/**//*
ID: lorelei3
TASK: fc
LANG: C++
*/

#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>

using namespace std;

const int STACKSIZE = 1000;
const int MAXN = 10001;
const int INF = 0x7FFFFFFF;


struct Point
{
double x,y;
};

ifstream fin("fc.in");
ofstream fout("fc.out");

Point p0, points[MAXN];


double cross(Point &p1s, Point &p1e, Point &p2s, Point &p2e)
{
double x1 = p1e.x - p1s.x;
double y1 = p1e.y - p1s.y;

double x2 = p2e.x - p2s.x;
double y2 = p2e.y - p2s.y;

return x1*y2-x2*y1;
}


double dis(Point &p1, Point &p2)
{
return sqrt((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));
}


int cmp(const void *A, const void *B)
{
Point *p1 = (Point*)A;
Point *p2 = (Point*)B;

double res = cross(p0, *p1, p0, *p2);
if(res>0)
return -1;
else if(res==0 && dis(p0,*p1) > dis(p0, *p2))
return -1;
else
return 1;
}

int n;

void input()
{
int loc=0;
double minx = INF, miny = INF;
fin>>n;

for(int i=0; i<n; ++i)
{
fin>>points[i].x >>points[i].y;

if(points[i].y < miny)
{
miny = points[i].y;
minx = points[i].x;
p0 = points[i];
loc = i;

}else if(points[i].y == miny)
{

if(points[i].x < minx)
{
miny = points[i].y;
minx = points[i].x;
p0 = points[i];
loc = i;
}
}
}
points[loc] = points[--n];

qsort(points, n, sizeof(Point), cmp);
}

Point stack[STACKSIZE];
int top;

void graham()
{

stack[++top] = p0;
stack[++top] = points[0];
stack[++top] = points[1];


for(int i=2; i<n; ++i)
{
while(cross(stack[top], points[i], stack[top], stack[top-1])<0 )
top--;
stack[++top] = points[i];
}
}

double ans=0;

void output()
{
int tmp = top;

while(tmp!=1)
{
ans += dis(stack[tmp], stack[tmp-1]);
tmp--;
}

ans += dis(p0, stack[top]);
fout.setf(ios::fixed);
fout.precision(2);
fout<<ans<<endl;

}


int main()
{

input();

graham();

output();

return 0;
}


posted on 2011-02-05 22:16
小阮 阅读(188)
评论(0) 编辑 收藏 引用 所属分类:
USACO