bzoj 1007 半交平面简化版

本题就是求半交平面的交包含哪些直线，而且有点特殊（一般的半交平面用双端队列，因为可能转到最开始的直线，但本题不会，所以只需要一端操作就行了）。

 /**************************************************************

     Problem: 1007

     User: idy002

     Language: C++

     Result: Accepted

     Time:184 ms

     Memory:2960 kb

 ****************************************************************/

 #include <cstdio>

 #include <algorithm>

 #define eps 1e-10

 #define maxn 50010

 using namespace std;

 int sg( double x ) {

     return (x>-eps)-(x<eps);

 }

 struct Vector {

     double x, y;

     Vector(){}

     Vector( double x, double y ) : x(x), y(y){}

 };

 typedef Vector Point;

 struct Line {

     int k, b;

     int id;

     Line(){}

     Line( int k, int b, int id ) : k(k), b(b), id(id) {}

     bool operator<( const Line & c ) const {

         return k<c.k || ( k==c.k && b>c.b );

     }

     bool operator==( const Line & c ) const {

         return k==c.k;

     }

     bool contain( const Point & p ) const {

         return sg(k*p.x+b-p.y)<;

     }

     Point operator&( const Line & l ) const {

         double x = 1.0 * (l.b-b) / (k-l.k);

         return Point(x,x*l.k+l.b);

     }

 };

 int n;

 Line ln[maxn];

 int ans[maxn];

 void calc() {

     static Line dql[maxn];

     static Point dqp[maxn];

     int beg, end;

     sort( ln, ln+n );

     n = unique( ln, ln+n ) - ln;

     dql[ beg = end =  ] = ln[];

     for( int i=; i<n; i++ ) {

         while( end-beg> && !ln[i].contain(dqp[end-]) ) end--;

         end++;

         dql[end] = ln[i];

         dqp[end-] = dql[end-]&dql[end];

     }

     int cnt = ;

     for( int i=beg; i<=end; i++ )

         ans[cnt++] = dql[i].id;

     sort( ans, ans+cnt );

     for( int i=; i<cnt; i++ )

         printf( "%d ", ans[i] );

 }

 int main() {

     scanf( "%d", &n );

     for( int i=; i<n; i++ )  {

         scanf( "%d%d", &ln[i].k, &ln[i].b );

         ln[i].id = i+;

     }

     calc();

 }