我希望你是我独家记忆

一段永远封存的记忆,随风而去
posts - 263, comments - 31, trackbacks - 0, articles - 3
   :: 首页 :: 新随笔 ::  :: 聚合  :: 管理
//3348 Accepted 264K 0MS C++ 4016B 
//典型的凸包和计算多边形面积

#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
#include 
<ctype.h>
#include 
<math.h>
#include 
<iostream>
using namespace std ;
#define unllong unsigned long long 
#define unint unsigned int
#define printline  printf( "\n" ) 
typedef 
long long llong ;
//const double PI = 2.0 * acos( 0.0 ) ;
#define zero(x) (((x)>0?(x):-(x))<eps)

const int Base=1000000000;//高精度
const int Capacity=100;//高精度
const double eps = 1e-8 ;
const int INF = 1000000 ;

const int size = 10010 ;

struct POINT
{
    
double x ;
    
double y ;
    
double k ;
};
struct POINT point[size] ;

int stack[size] ; 
int top = 2 ;

int inn ;
double outarea ;

double fdist( double x1, double y1, double x2, double y2 )
{
    
return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ) ;
}

void input()
{
    
int leftdown = 0 ;
    
forint i=0; i<inn; i++ ) {
        scanf( 
"%lf %lf"&point[i].x, &point[i].y ) ;
        
//if( miny>point[i].y || miny==point[i].y&&minx>point[i].x )
        if( point[leftdown].y>point[i].y||zero(point[leftdown].y-point[i].y)&&point[leftdown].x>point[i].x )
            leftdown 
= i ;//找到最左下的点
    }
    
double temp ;
    temp 
= point[0].x ; point[0].x = point[leftdown].x ; point[leftdown].x = temp ;
    temp 
= point[0].y ; point[0].y = point[leftdown].y ; point[leftdown].y = temp ;
    
forint i=1; i<inn; i++ ) {
        point[i].k 
= atan2( point[i].y-point[0].y, point[i].x-point[0].x ) ;
    }
//以点(minx, miny)计算极角
}

double xmult( POINT &p1, POINT &p2, POINT &p0 )
{
//计算叉乘--线段旋转方向和对应的四边形的面积--返回(p1-p0)*(p2-p0)叉积
    
//if叉积为正--p0p1在p0p2的顺时针方向; if(x==0)共线

    
return (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y) ;
}

int gramcmp1( const void *a, const void *b )
{
    
struct POINT *= (struct POINT *)a ;
    
struct POINT *= (struct POINT *)b ;

    
if( c->- d->> eps )    return 1 ;
    
else if( c->- d->< -1*eps ) return -1 ;
    
else//斜率相等距离远的点在先
        return c->- d->> 0 ? 1 : -1 ;
}

int gramcmp( const void *a, const void *b )
{
    
struct POINT *= (struct POINT *)a ;
    
struct POINT *= (struct POINT *)b ;

    
double xmult_val = xmult( *c, *d, point[0] ) ;
    
if( xmult_val > eps )    return -1 ;
    
else if( xmult_val < -1*eps ) return 1 ;
    
else return c->- d->> 0 ? 1 : -1 ;
    
//else 
    
//return fdist( c->x,c->y,point[0].x,point[0].y )>fdist(d->x,d->y,point[0].x,point[0].y)? -1:1 ;
}

void gramham()
{
//凸包的点存在于stack[]中
    qsort( point+1, inn-1sizeof(point[1]), gramcmp ) ;//极坐标排序--注意只有(n-1)个点

    
//int stack[size] ; int top = 2 ;
    stack[0= 0 ; stack[1= 1 ; stack[2= 2 ; top  = 2 ;

    
forint i=3; i<inn; i++ )
    {
        
while( top>=1&&xmult( point[i], point[stack[top]], point[stack[top-1]] )>=-1*eps ) 
            top
-- ;//顺时针方向--删除栈顶元素
        stack[++top] = i ;//新元素入栈
    }
    
/*
    for( int i=0; i<=top; i++ )
    {
    //printf( "%lf===%lf\n",point[stack[i]].x, point[stack[i]].y ) ;
    cout << point[stack[i]].x << "====" << point[stack[i]].y << endl ;
    }
    
*/
}

double flen_poly()
{
//计算凸包的周长
    double len = 0.0 ; double x1, x2, y1, y2 ;
    
forint i=0; i<top; i++ ) {
        x1 
= point[stack[i+1]].x ; x2 = point[stack[i]].x ;
        y1 
= point[stack[i+1]].y ; y2 = point[stack[i]].y ;
        len 
+= fdist( x1, y1, x2, y2 ) ;
    }
    x1 
= point[stack[0]].x ; x2 = point[stack[top]].x ;
    y1 
= point[stack[0]].y ; y2 = point[stack[top]].y ;
    len 
+= fdist( x1, y1, x2, y2 ) ;

    
return len ;
}

double farea_poly( int n, POINT poly[] )
{
    
double area = 0.0 ; double s1 = 0.0 , s2 = 0.0 ;
    
forint i=0; i<n; i++ )
    {
        s1 
+= poly[stack[(i+1)%n]].y * poly[stack[i%n]].x ;
        s2 
+= poly[stack[(i+1)%n]].y * poly[stack[(i+2)%n]].x ;
    }

    
return fabs( s1 - s2 ) / 2 ;
}

void process()
{
    gramham() ;
//保存好凸包的点在stack[]中

    outarea 
= farea_poly( top+1, point ) ;
}

void output()
{
    printf( 
"%d\n", (int)outarea/50 ) ;
}

int main()
{
    
//freopen( "fc.in", "r", stdin ) ;
    
//freopen( "fc.out","w",stdout ) ;

    
//freopen( "in.txt", "r", stdin ) ;

    
while( scanf( "%d"&inn ) != EOF ) 
    {
        input() ;

        process() ;

        output() ;
    }

    
return 0 ;
}

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