凸包入门题目, 我用的是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
小阮 阅读(172)
评论(0) 编辑 收藏 引用 所属分类:
USACO