bzoj1007-水平可见直线
2024-09-04 09:39:42
题目
在平面直角坐标系上以\(y=kx+b\)的形式给出\(n (n\le 50000)\)条直线,求从无限高的地方能看到多少条直线。
分析
举几个例子发现我们要求的直线组成一个下凸的形状。所以我们只要找出直线围成的下凸包即可。
对直线排序,\(k\)从小到大,\(b\)从大到小,用一个栈维护一下。如果当前元素与栈顶元素的交点在栈顶元素与栈中第二个元素的交点的左边,那么弹出栈顶(模拟一下就知道了)。
代码
计算几何尽量避免除法,因为会有精度问题,一般移项转化成乘法计算。
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=5e4+10;
struct line {
double k,b;
int id;
bool operator < (const line a) const {
return k==a.k?b>a.b:k<a.k;
}
} a[maxn],sta[maxn];
int top=0;
bool bid(line a,line b) {
return a.id<b.id;
}
bool ans[maxn];
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
int n;
scanf("%d",&n);
for (int i=1;i<=n;++i) scanf("%lf%lf",&a[i].k,&a[i].b),a[i].id=i;
sort(a+1,a+n+1);
for (int i=1;i<=n;++i) {
while (top>1) if ((a[i].b-sta[top].b)*(sta[top-1].k-sta[top].k)<=(sta[top].b-sta[top-1].b)*(sta[top].k-a[i].k)) --top; else break;
sta[++top]=a[i];
}
for (int i=1;i<=top;++i) ans[sta[i].id]=true;
for (int i=1;i<maxn;++i) if (ans[i]) printf("%d ",i);
puts("");
}
最新文章
- memcached 的简介、安装、命令
- 模拟赛1030d2
- ios图标和默认图像
- Maven学习小结(三 基本概念)
- ARM学习笔记7——乘法指令
- SqlBulkCopy的一个例子
- VLC播放器架构剖析
- MySQL多Text字段报8126错误(解决过程)
- docker搭建私服
- GDB调试指南-启动调试
- 对strom的理解
- 以Attribute加上Header验证
- Ue4管线中的灯光信息
- Struts2第三天
- ora-24550 signo=6 signo=11解决
- [UnityShader基础]01.渲染队列
- bzoj千题计划228:bzoj2095: [Poi2010]Bridges
- UINavigationItem 设置UIBarButtonItem
- 绘制pathway富集散点图
- Shell脚本编写规范