BZOJ1007.[HNOI2008]水平可见直线

可见的直线为一下凸壳。

先按斜率和截距从小到大排序，再用单调栈判断交点的相对位置即可。

#include
const int N = 5e4 + 7;
const double eps = 1e-7;
inline int dcmp(double x) {
if (fabs(x) return x <0 ? -1 : 1;
}
struct P {
double x, y;
int id;
inline bool operator <(const P &rhs) const {
if (dcmp(x - rhs.x) == 0) return y return x }
} p[N];
int st[N], top;
inline double crossx(const P &a, const P &b) {
return (a.y - b.y) / (b.x - a.x);
}
void ins(int id) {
const P &cur = p[id];
while (top) {
if (dcmp(p[st[top]].x - cur.x) == 0) top--;
else if (top > 1 && dcmp(crossx(p[st[top]], cur) - crossx(p[st[top]], p[st[top - 1]])) <= 0) top--;
else break;
}
st[++top] = id;
}
int ans[N];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lf%lf", &p[i].x, &p[i].y);
p[i].id = i;
}
std::sort(p + 1, p + 1 + n);
for (int i = 1; i <= n; i++)
ins(i);
for (int i = 1; i <= top; i++)
ans[p[st[i]].id] = 1;
for (int i = 1; i <= n; i++)
if (ans[i])
printf("%d ", i);
return 0;
}
View Code