学步园

传送门：【HDU】4946 Area of Mushroom

题目分析：赤裸裸的凸包，因为速度最大的点一定比速度小的跑的快，所以一段时间以后速度大的点一定能比速度小的点先到远处，所以如果可能有无限面积的优先考虑速度最大的。然后，如果多个人速度最大，那么被包围在其他速度大的人里面的面积一样不会是无限的，所以只要对速度大的人求一次凸包即可。并且如果速度最大的人速度为零，则所有人的面积都不是无限的。

这次失策，在求凸包的时候考虑到重复点的问题，但是没有去掉，导致一直wa，最后弃疗去重交了一发竟然AC。。仔细想想也是，如果有两个点在同一位置，那么排在这两个点之后的点和这两个点形成的叉积一定等于0（因凸包为一条边上有多个点则这多个点的面积都应该是无限的，所以当叉积为0的时候我们也算这个点暂时属于凸包），那么最后算法很可能得到一个“凹包”。。。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>  
using namespace std ;

#define REP( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )

const int MAXN = 2333 ;

struct Point {
	int x , y ;
	int idx , v ;
	bool flag ;
	Point ( int x = 0 , int y = 0 ) : x ( x ) , y ( y ) {}
	Point operator - ( const Point &b ) const {
		return Point ( x - b.x , y - b.y ) ;
	}
	void input ( int &_idx ) {
		scanf ( "%d%d%d" , &x , &y , &v ) ;
		idx = _idx ;
		flag = 0 ;
	}
} p[MAXN] ;

bool res[MAXN] ;
int S[MAXN] , top ;
int n ;

int Cross ( const Point &A , const Point &B ) {
	return A.x * B.y - A.y * B.x ;
}

int cmp1 ( const Point &a , const Point &b ) {
	if( a.x != b.x ) return a.x < b.x ;
	else if ( a.y != b.y ) return a.y < b.y ;
	else return a.v > b.v ;
}

int cmp2 ( const Point &a , const Point &b ) {
	return a.v > b.v ;
}

int ConvexHull ( Point* p , int n ) {
	top = 0 ;
	sort ( p , p + n , cmp1 ) ;
	REP ( i , 0 , n - 1 )
		if ( p[i].x == p[i + 1].x && p[i].y == p[i + 1].y && p[i].v == p[i + 1].v )
			p[i].flag = 1 ;
	REP ( i , 0 , n ) {
		if ( p[i].flag ) continue ;
		while ( top > 1 && Cross ( p[S[top - 1]] - p[S[top - 2]] , p[i] - p[S[top - 2]] ) < 0 ) -- top ;
		S[top ++] = i ;
	}
	int k = top ;
	REV ( i , n - 2 , 0 ) {
		if ( p[i].flag ) continue ;
		while ( top > k && Cross ( p[S[top - 1]] - p[S[top - 2]] , p[i] - p[S[top - 2]] ) < 0 ) -- top ;
		S[top ++] = i ;
	}
	if ( n > 1 ) -- top ;
	return top ;
}

void solve () {
	CLR ( res , 0 ) ;
	REP ( i , 0 , n ) p[i].input ( i ) ;
	sort ( p , p + n , cmp2 ) ;
	if ( !p[0].v ) {
		REP ( i , 0 , n ) printf ( "0" ) ;
		printf ( "\n" ) ;
		return ;
	}
	int m ;
	for ( m = 0 ; m < n - 1 ; ++ m ) if ( p[m].v != p[m + 1].v ) break ;
	m = ConvexHull ( p , m + 1 ) ;
	REP ( i , 0 , m ) res[p[S[i]].idx] = 1 ;
	sort ( p , p + n , cmp1 ) ;
	REP ( i , 0 , n - 1 )
		if ( p[i].x == p[i + 1].x && p[i].y == p[i + 1].y && p[i].v == p[i + 1].v )
			res[p[i].idx] = res[p[i + 1].idx] = 0 ;
	REP ( i , 0 , n ) printf ( "%d" , res[i] ) ;
	printf ( "\n" ) ;
}

int main () {
	int cas = 0 ;
	while ( ~scanf ( "%d" , &n ) && n ) {
		printf ( "Case #%d: ", ++ cas ) ;
		solve () ;
	}
	return 0 ;
}