BZOJ-1007: [HNOI2008]水平可见直线

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1007

按照斜率升序排序，然后用栈维护一下就可以了。。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std ;
 
#define MAXN 50010
 
struct pos {
            int k , b , t ;
            bool operator < ( const pos x ) const {
                        return ( k < x.k ) || ( k == x.k && b > x.b ) ;
            }
} a[ MAXN ] ;
 
int n , ans[ MAXN ] ;
int S[ MAXN ] , top = 0 ;
 
int main(  ) {
            scanf( "%d" , &n ) ;
            for ( int i = 0 ; i ++ < n ; )scanf( "%d%d" , &a[ i ].k , &a[ i ].b ) , a[ i ].t = i ;
            sort( a + 1 , a + n + 1 ) ;
            for ( int i = 0 ; i ++ < n ; ) {
                        if ( top && a[ S[ top ] ].k == a[ i ].k ) continue ;
                        while ( top > 1 ) {
                                     double x = double( a[ i ].b - a[ S[ top ] ].b ) / double( a[ S[ top ] ].k - a[ i ].k ) ;
                                     double y = a[ i ].k * x + a[ i ].b ;
                                     if ( a[ S[ top - 1 ] ].k * x + a[ S[ top - 1 ] ].b >= y ) {
                                                 top -- ;
                                    } else break ;
                        }
                        S[ ++ top ] = i ;
            }
            for ( int i = 0 ; i ++ < top ; ) ans[ i ] = a[ S[ i ] ].t ;
            sort( ans + 1 , ans + top + 1 ) ;
            for ( int i = 0 ; i ++ < top ; )printf( "%d " , ans[ i ] ) ;printf( "\n" ) ;
            return 0 ;
}