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();
}
上一篇:js将字符串转变成数字


下一篇:iOS MVVM 参考