随笔-141  评论-9  文章-3  trackbacks-0

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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理