Posted on 2008-08-18 14:41
Hero 阅读(1027)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
//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 ;
for( int 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 ;
for( int 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 *c = (struct POINT *)a ;
struct POINT *d = (struct POINT *)b ;
if( c->k - d->k > eps ) return 1 ;
else if( c->k - d->k < -1*eps ) return -1 ;
else//斜率相等距离远的点在先
return c->x - d->x > 0 ? 1 : -1 ;
}
int gramcmp( const void *a, const void *b )
{
struct POINT *c = (struct POINT *)a ;
struct POINT *d = (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->x - d->x > 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-1, sizeof(point[1]), gramcmp ) ;//极坐标排序--注意只有(n-1)个点
//int stack[size] ; int top = 2 ;
stack[0] = 0 ; stack[1] = 1 ; stack[2] = 2 ; top = 2 ;
for( int 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 ;
for( int 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 ;
for( int 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 ;
}