Posted on 2008-08-18 16:06
Hero 閱讀(413)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
//1113 Accepted 452K 63MS G++ 4131B
//典型的凸包--注意xmult相同的時候按點從遠到進排序
#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 ;
#define zero(x) (((x)>0?(x):-(x))<eps)
const int Base=1000000000;//高精度
const int Capacity=100;//高精度
const double PI = 2.0*acos( 0.0 ) ;
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; int inr ;
double outarea ;
double outlen ;
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]), gramcmp1 ) ;//極坐標排序--注意只有(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[]中
outlen = flen_poly() ;
outlen += PI * 2.0 * inr ;
}
void output()
{
printf( "%0.0lf\n", outlen ) ;
}
int main()
{
//freopen( "fc.in", "r", stdin ) ;
//freopen( "fc.out","w",stdout ) ;
//freopen( "in.txt", "r", stdin ) ;
//while( scanf( "%d %d", &inn, &inr ) != EOF )
scanf( "%d %d", &inn, &inr ) ;
{
input() ;
process() ;
output() ;
}
return 0 ;
}