凸包问题的一个应用,地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=1228
#include < stdio.h >
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include < stdlib.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) {
int x;
int y;
int addr;
int flag;
}type;
type p[1005];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int stack[1001];
int top;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int e[1001];
int now;
![](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 initf( 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)
now = 1;
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
e[i] = 0;
}
}
![](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)
int 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)
int x1 = a->x - b->x;
int y1 = a->y - b->y;
int x2 = c->x - d->x;
int 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)
int 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)
int x = a->x - b->x;
int 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 = - mul( c, &p[0], d, &p[0] );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( ans==0 )
![](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)
initf( n+1 );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
inits();
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) {
if ( mul( &p[i], &p[stack[top-1]], &p[stack[top]], &p[stack[top-1]] ) >= 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( mul( &p[i], &p[stack[top-1]], &p[stack[top]], &p[stack[top-1]] ) == 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
e[now] ++;
}
p[stack[top]].flag = 0;
out();
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
now ++;
}
in( i );
p[i].flag = 1;
}
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( mul( &p[i], &p[stack[top-1]], &p[stack[top]], &p[stack[top-1]] ) >= 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( mul( &p[i], &p[stack[top-1]], &p[stack[top]], &p[stack[top-1]] ) == 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
e[now] ++;
}
p[stack[top]].flag = 0;
out();
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
now ++;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
in( n-1 );
p[n-1].flag = 1;
now ++;
![](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, t;
int i;
int ans;
scanf( "%d", &t );
while ( t-- )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf( "%d", &n );
for ( i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf( "%d%d", &p[i].x, &p[i]. y );
p[i].addr = i;
p[i].flag = 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( n < 3 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf( "NO\n" );
continue;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( !aobao( n ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf( "NO\n" );
continue;
}
![](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;
}
}
if ( i > 1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
e[0] = i;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( i=n-2; i>0; 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;
}
}
if ( n-i > 2 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
e[now] = n-i;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ans = 1;
for( i=0; i<=now; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
ans *= e[i];
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if( ans )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf( "YES\n" );
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf( "NO\n" );
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
![](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)
阅读排行榜
评论排行榜
|
|