bzoj 1007 半交平面简化版

 1 /**************************************************************
 2     Problem: 1007
 3     User: idy002
 4     Language: C++
 5     Result: Accepted
 6     Time:184 ms
 7     Memory:2960 kb
 8 ****************************************************************/
 9  
10 #include <cstdio>
11 #include <algorithm>
12 #define eps 1e-10
13 #define maxn 50010
14 using namespace std;
15  
16 int sg( double x ) {
17     return (x>-eps)-(x<eps);
18 }
19 struct Vector {
20     double x, y;
21     Vector(){}
22     Vector( double x, double y ) : x(x), y(y){}
23 };
24 typedef Vector Point;
25 struct Line {
26     int k, b;
27     int id;
28     Line(){}
29     Line( int k, int b, int id ) : k(k), b(b), id(id) {}
30     bool operator<( const Line & c ) const {
31         return k<c.k || ( k==c.k && b>c.b );
32     }
33     bool operator==( const Line & c ) const {
34         return k==c.k;
35     }
36     bool contain( const Point & p ) const {
37         return sg(k*p.x+b-p.y)<0;
38     }
39     Point operator&( const Line & l ) const {
40         double x = 1.0 * (l.b-b) / (k-l.k);
41         return Point(x,x*l.k+l.b);
42     }
43 };
44  
45 int n;
46 Line ln[maxn];
47 int ans[maxn];
48  
49 void calc() {
50     static Line dql[maxn];
51     static Point dqp[maxn];
52     int beg, end;
53  
54     sort( ln, ln+n );
55     n = unique( ln, ln+n ) - ln;
56     dql[ beg = end = 0 ] = ln[0];
57     for( int i=1; i<n; i++ ) {
58         while( end-beg>0 && !ln[i].contain(dqp[end-1]) ) end--;
59         end++;
60         dql[end] = ln[i];
61         dqp[end-1] = dql[end-1]&dql[end];
62     }
63     int cnt = 0;
64     for( int i=beg; i<=end; i++ )
65         ans[cnt++] = dql[i].id;
66     sort( ans, ans+cnt );
67     for( int i=0; i<cnt; i++ )
68         printf( "%d ", ans[i] );
69 }
70  
71 int main() {
72     scanf( "%d", &n );
73     for( int i=0; i<n; i++ )  {
74         scanf( "%d%d", &ln[i].k, &ln[i].b );
75         ln[i].id = i+1;
76     }
77     calc();
78 }
79