BZOJ1007:[HNOI2008]水平可见直线(计算几何)
2024-10-18 23:35:31
Description
在xoy直角坐标平面上有n条直线L1,L2,...Ln,若在y值为正无穷大处往下看,能见到Li的某个子线段,则称Li为
可见的,否则Li为被覆盖的.
例如,对于直线:
L1:y=x; L2:y=-x; L3:y=0
则L1和L2是可见的,L3是被覆盖的.
给出n条直线,表示成y=Ax+B的形式(|A|,|B|<=500000),且n条直线两两不重合.求出所有可见的直线.
Input
第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi
Output
从小到大输出可见直线的编号,两两中间用空格隔开,最后一个数字后面也必须有个空格
Sample Input
3
-1 0
1 0
0 0
-1 0
1 0
0 0
Sample Output
1 2
Solution
首先把直线按照斜率排序,再用个栈维护一下。
画个图可以发现,如果直线$i$和直线$stack[top]$的交点在直线$stack[top-1]$的左边,那么$stack[top]$就可以被弹出了。随便判判就好了。
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N (50009)
#define INF (1e18)
using namespace std; struct Vector
{
double x,y;
Vector(double xx=,double yy=)
{
x=xx; y=yy;
}
}p[N];
typedef Vector Point; struct Line
{
double k,b;
Point x,y;
int id;
bool operator < (const Line &a) const
{
return k==a.k?b>a.b:k>a.k;
}
bool operator == (const Line &a) const
{
return k==a.k && b==a.b;
}
}L[N],stack[N]; int n,k,b,ans[N],top; double Cross(Vector a,Vector b) {return a.x*b.y-a.y*b.x;}
Vector operator - (Vector a,Vector b) {return Vector(a.x-b.x,a.y-b.y);} inline int read()
{
int x=,w=; char c=getchar();
while (!isdigit(c)) {if (c=='-') w=-; c=getchar();}
while (isdigit(c)) x=x*+c-'', c=getchar();
return x*w;
} Point Line_Cross(Line u,Line v)
{
Point ans;
ans.x=(v.b-u.b)/(u.k-v.k);
ans.y=u.k*ans.x+u.b;
return ans;
} int main()
{
n=read();
for (int i=; i<=n; ++i)
{
k=read(); b=read();
L[i]=(Line){k,b};
L[i].x=(Point){,b};
L[i].y=(Point){,k+b};
L[i].id=i;
}
sort(L+,L+n+);
for (int i=; i<=n; ++i)
{
if (top && L[i].k==stack[top].k) continue;
while (top>=)
{
Point p=Line_Cross(stack[top],L[i]);
if (Cross(stack[top-].x-p,stack[top-].y-p)>) break;
top--;
}
stack[++top]=L[i];
}
for (int i=; i<=top; ++i) ans[stack[i].id]=;
for (int i=; i<=n; ++i) if (ans[i]) printf("%d ",i);
}
最新文章
- Apache的初中级面试题
- Supervisor重新加载配置
- BackTrack5-r3任务栏显示网络图标及自定义DNS
- Rails : css或js文件无法成功预编译或调用jquery类插件时预编译问题
- 我心中的核心组件(可插拔的AOP)~第五回 消息组件
- JS this,call和apply以及回调函数
- a标签属性说明
- HTML -- 元素和属性
- go与json
- delphi数字签名验证及能够获取数字签名文件信息(利用wintrust.dll的导出函数,翻译一下)
- java 不寻常的问题 No bean named &;#39;sessionFactory&;#39; is defined 和 initialize a collection of role
- Java 读书笔记 (十) 循环
- Android八门神器(一): OkHttp框架源码解析
- 特性Attribute
- 如何使用grep 等命令快速的在日志中找到自己需要的内容
- 【莫比乌斯反演】HDU1695_GCD
- VC设置视图背景颜色方法
- 20145305 《网络对抗》注入Shellcode并执行&;Return-to-libc 攻击实验
- pycharm 提示性信息
- 测试这个才可以打包 我的PYQt matplotlib numpy 等程序
热门文章
- vs2013 在win7下,使用c++创建项目各种报错问题解决方案
- CSS学习笔记02 CSS选择器
- Fork/Join 框架-设计与实现(翻译自论文《A Java Fork/Join Framework》原作者 Doug Lea)
- 【Tomcat】JVM,Tomcat,Servlet,Tomcat中的应用。彻底弄懂这些概念之间的联系
- JAVA设计模式详解(二)----------观察者模式
- 本地服务器搭建服务:ftp
- JS 关于this p9
- Navicat Premium 12连接Oracle时提示oracle library is not loaded的问题解决
- 使用Webpack对Css文件压缩处理的思考
- maven 学习笔记--仓库,聚合和继承,私服搭建