描述


http://www.lydsy.com/JudgeOnline/problem.php?id=1007

给出一些直线,沿着y轴从上往下看,能看到多少条直线.

分析


由于直线相交,会遮挡住一些直线.

自己画画图就可以发现,最后能看见的直线,也就是在最上面的那些直线一定构成一个凸包的下凸壳(没错一定是凸的).

接下来就是如何求这个下凸壳了.

先按照斜率为第一关键字,截距为第二关键字,将直线从小到大排序.用一个斜率单调递增的栈来维护凸壳.

我们按照排序后的顺序添加直线,画画图会发现:

1.斜率相同的直线,截距小的会被覆盖.

2.如果第i条直线之前有>=2条直线,那么第i条直线与第(i-1)条直线的交点p,第(i-1)条直线与第(i-2)条直线的交点q,有这样的关系:

(1).如果p在q右边,那么第i条直线可以直接加进来.

(2).如果p在q左边或者p与q重合,那么第(i-1)条直线会被第i条直线覆盖.

 #include <bits/stdc++.h>
using namespace std; const int maxn=+;
const double eps=1e-;
int n,top;
int s[maxn];
bool mark[maxn];
struct line{
double k,b;
int id;
bool operator < (const line &a) const{
if(fabs(a.k-k)<eps) return b<a.b;
return k<a.k;
}
}l[maxn];
inline double crossx(line x,line y){ return (x.b-y.b)/(y.k-x.k); }
void insert(int x){
while(top){
if(fabs(l[x].k-l[s[top]].k)<eps) top--;
else if(top>&&crossx(l[x],l[s[top]])<=crossx(l[s[top]],l[s[top-]])) top--;
else break;
}
s[++top]=x;
}
void init(){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%lf%lf",&l[i].k,&l[i].b), l[i].id=i;
sort(l+,l+n+);
}
int main(){
init();
for(int i=;i<=n;i++) insert(i);
for(int i=;i<=top;i++) mark[l[s[i]].id]=true;
for(int i=;i<=n;i++)if(mark[i]) printf("%d ",i);
return ;
}

1007: [HNOI2008]水平可见直线

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 5631  Solved: 2138
[Submit][Status][Discuss]

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

Sample Output

1 2

HINT

Source

最新文章

  1. codeforces Round #320 (Div. 2) C. A Problem about Polyline(数学) D. &quot;Or&quot; Game(暴力,数学)
  2. xcode 常见错误报错问题!
  3. iOS 推送小记
  4. xp下安装jdk8
  5. iOS多线程-02-GCD
  6. Oracle 性能查看
  7. 【转载】wireshark:no interface can be used for capturing in this system with the current configuration
  8. Makefile 如何轻松搞定
  9. 10---Net基础加强
  10. oracle11g密码大小写敏感问题
  11. UIWindow详解
  12. CSS3随笔系列之transform(一)—— transform-origin
  13. oracle获取本月第一天和最后一天及Oracle trunc()函数的用法
  14. iOS viewController添加导航条以及返回跳转选择
  15. Facebook开源的基于SQL的操作系统检测和监控框架:osquery Table详解
  16. python apschedule安装使用与源码分析
  17. [MicroPython]TPYBoardv102播放音乐实例
  18. BZOJ.1109.[POI2007]堆积木Klo(DP LIS)
  19. C++ Programming Language中的narrow_cast实现
  20. wx python 基本控件

热门文章

  1. Mysql 的变量
  2. Python 问题集
  3. 第33条:用EnumMap代替序数索引
  4. vmware workstation下的虚拟Linux通过NAT模式共享上网
  5. Linux EMACS的简单使用
  6. 出力csv
  7. vmware RHEL6.x 开启FTP和TELNET服务--root权限
  8. 工作踩坑记录:JavaScript跳转被缓存
  9. 安装IntelliJ IDEA热部署tomcat插件JreBel
  10. Python 基础篇:编码、变量、模块