xfstart07
Get busy living or get busy dying

/*
PROG: fc
LANG: C++
*/
#include
< iostream >
#include
< cmath >
#include
< cstdlib >
using   namespace  std;

typedef 
struct {
    
double  x,y;
}Point;
int  N,top;
Point P[
10001 ], * stack[ 10001 ],ST;
double  FP(Point  & l1s,Point  & l1e,Point &  l2s,Point  & l2e)
{
    Point 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;
}
inline 
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){
    Point 
* a = (Point * )A, * b = (Point * )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()
{
    scanf(
" %d " , & N);
    
double  max1 =- 0xFFFFFFF ;
    
int  st;
    
for ( int  i = 1 ;i <= N; ++ i){
        scanf(
" %lf%lf " , & P[i].x, & P[i].y);
        
if (P[i].x > max1){
            max1
= P[i].x;
            ST
= P[i];
            st
= i;
        }
    }
    P[st]
= P[N];  N -- ;
    qsort(P
+ 1 ,N, sizeof (Point),cmp);
}
void  graham()
{
    stack[
0 ] =& ST;
    stack[top
= 1 ] =& P[ 1 ];
    
for ( int  i = 2 ;i <= N; ++ i){
        stack[
++ top] =& P[i];
        
while (FP( * stack[top], * stack[top - 1 ], * stack[top - 2 ], * stack[top]) < 0 )
        {
            stack[top
- 1 ] = stack[top];
            top
-- ;
        }
    }
}
void   out ()
{
    
double  res = 0 ;
    
for ( int  i = 1 ;i <= top; ++ i)
        res
+= dis(stack[i - 1 ] -> x,stack[i - 1 ] -> y,stack[i] -> x,stack[i] -> y);
    res
+= dis(stack[top] -> x,stack[top] -> y,stack[ 0 ] -> x,stack[ 0 ] -> y);
    printf(
" %0.2lf\n " ,res);
}
int  main()
{
    freopen(
" fc.in " , " r " ,stdin);
    freopen(
" fc.out " , " w " ,stdout);
    init();
    graham();
    
out ();
    
return   0 ;
}
/*
Executing
   Test 1: TEST OK [0.011 secs, 3016 KB]
   Test 2: TEST OK [0.000 secs, 3148 KB]
   Test 3: TEST OK [0.000 secs, 3148 KB]
   Test 4: TEST OK [0.000 secs, 3148 KB]
   Test 5: TEST OK [0.011 secs, 3148 KB]
   Test 6: TEST OK [0.022 secs, 3148 KB]
   Test 7: TEST OK [0.032 secs, 3148 KB]
   Test 8: TEST OK [0.043 secs, 3148 KB]
*/



posted on 2009-07-14 16:28 xfstart07 阅读(159) 评论(0)  编辑 收藏 引用

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