昨天晚上太卡了,竟然没有全部发完,今天早上早早起来发一下,1113是一个计算几何的题目,求得是凸包问题,就是在二维平面上给定一系列的点,求一个最小的凸包将它们全部覆盖,所谓凸包就是一个多边形,在这个多边形内的任意两点间的连线都在多边形内。地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=1113
#include < stdio.h >
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include < stdlib.h >
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include < math.h >
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
double x;
double y;
int addr;
int flag;
}type;
type p[1005];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int stack[1005];
int top;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void inits( )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
top = -1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void in( int a )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
stack[++top] = a;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void out()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
top --;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void f_min( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i;
type min;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
min.x = p[0].x;
min.y = p[0].y;
min.addr = p[0].addr;
min.flag = p[0].flag;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( i=1; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( min.y > p[i].y )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
min.x = p[i].x;
min.y = p[i].y;
min.addr = p[i].addr;
min.flag = p[i].flag;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( min.y == p[i].y )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( min.x > p[i].x )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
min.x = p[i].x;
min.y = p[i].y;
min.addr = p[i].addr;
min.flag = p[i].flag;
}
}
}
}
p[min.addr].x = p[0].x;
p[min.addr].y = p[0].y;
p[min.addr].addr = p[0].addr;
p[min.addr].flag = p[0].flag;
p[0].x = min.x;
p[0].y = min.y;
p[0].addr = min.addr;
p[0].flag = min.flag;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
double mul( type *a, type *b, type *c, type *d )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
double x1 = a->x - b->x;
double y1 = a->y - b->y;
double x2 = c->x - d->x;
double y2 = c->y - d->y;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return x1 * y2 - x2 * y1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
double dis( type *a, type *b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
double x = a->x - b->x;
double y = a->y - b->y;
return x*x + y*y;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int cmp( const void *a, const void *b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
type *c = ( type * )a;
type *d = ( type * )b;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int ans;
if ( mul( c, &p[0], d, &p[0] ) > 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
ans = -1;
}
else if ( mul( c, &p[0], d, &p[0] ) < 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
ans = 1;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( dis( c, &p[0] ) > dis( d, &p[0] ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
ans = 1;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( dis( c, &p[0] ) < dis( d, &p[0] ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
ans = -1;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return ans;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int aobao( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i;
int ans = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
f_min( n );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
qsort( p+1, n-1, sizeof( type ), cmp );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
inits();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
in( 0 );
p[0].flag = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( i=1; i<n-1; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( mul( &p[i], &p[0], &p[i+1], &p[0] ) != 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
break;
}
}
in( i );
p[i].flag = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( i == n-1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
ans = 0;
return ans;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( ++i; i<n-1; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( mul( &p[i], &p[0], &p[i+1], &p[0] ) != 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
break;
}
}
in( i );
p[i].flag = 1;
for ( ++i; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( i < n-1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( mul( &p[i], &p[0], &p[i+1], &p[0] ) != 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
while ( mul( &p[i], &p[stack[top-1]], &p[stack[top]], &p[stack[top-1]] ) >= 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
p[stack[top]].flag = 0;
out();
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
in( i );
p[i].flag = 1;
}
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
while ( mul( &p[i], &p[stack[top-1]], &p[stack[top]], &p[stack[top-1]] ) >= 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
p[stack[top]].flag = 0;
out();
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
in( i );
p[i].flag = 1;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return ans;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int n;
double l;
double ans;
int temp;
int i;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while ( scanf( "%d%lf", &n, &l ) != EOF )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for ( i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf( "%lf%lf", &p[i].x, &p[i].y );
p[i].addr = i;
p[i].flag = 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
temp = aobao( n );
ans = 0;
for ( i=1; i<=top; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
ans += sqrt( dis( &p[stack[i]], &p[stack[i-1]] ) );
}
if ( temp )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
ans += sqrt( dis( &p[stack[top]], &p[stack[0]] ) );
}
ans += 2 * l * acos(-1);
printf( "%d\n", ( int )( ans+0.5 ) );
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
|
|