水平可见直线 BZOJ 1007
2018-06-17 23:26:22来源:未知 阅读 ()
水平可见直线
【问题描述】
在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条直线两两不重合.求出所有可见的直线.
【输入格式】
第一行为N(0<N<50000),接下来的N行输入Ai,Bi
【输出格式】
从小到大输出可见直线的编号,两两中间用空格隔开,最后一个数字后面也必须有个空格
【样例输入】
3
-1 0
1 0
0 0
【样例输出】
1 2
题解:
1.对于斜率相同的两条直线截距小的被覆盖。
2.对于斜率不同的三条直线,如果一条直线不可见
那么必定是斜率最大和斜率最小的覆盖另外一条线段
同时斜率最大和斜率最小的直线的交点在另一条线段的上方
根据这个性质,通过排序和单调栈即可维护可见直线。
1 #include<algorithm>
2 #include<iostream>
3 #include<cstring>
4 #include<cstdlib>
5 #include<cstdio>
6 #include<cmath>
7 using namespace std;
8 inline int Get()
9 {
10 int x = 0, s = 1;
11 char c = getchar();
12 while('0' > c || c > '9')
13 {
14 if(c == '-') s = -1;
15 c = getchar();
16 }
17 while('0' <= c && c <= '9')
18 {
19 x = (x << 3) + (x << 1) + c - '0';
20 c = getchar();
21 }
22 return x * s;
23 }
24 int n;
25 struct shape
26 {
27 int a, b, i;
28 };
29 shape a[100233];
30 int s[100233];
31 int ans[100233];
32 inline bool rule(shape a, shape b)
33 {
34 if(a.a != b.a) return a.a > b.a;
35 return a.b > b.b;
36 }
37 inline double Sol(int x, int y)
38 {
39 return (double) (a[y].b - a[x].b) / (double) (a[x].a - a[y].a);
40 }
41 int main()
42 {
43 n = Get();
44 for(int i = 1; i <= n; ++i)
45 {
46 a[i].a = Get();
47 a[i].b = Get();
48 a[i].i = i;
49 }
50 sort(a + 1, a + 1 + n, rule);
51 int top = 0;
52 for(int i = 1; i <= n; ++i)
53 {
54 if(a[i].a == a[s[top]].a) continue;
55 while(top > 1 && Sol(s[top], i) >= Sol(s[top], s[top - 1]))
56 --top;
57 s[++top] = i;
58 ans[top] = a[i].i;
59 }
60 sort(ans + 1, ans + 1 + top);
61 for(int i = 1; i <= top; ++i) printf("%d ", ans[i]);
62 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 石子合并问题--直线版 HRBUST - 1818 2019-08-16
- 【OpenCV3】直线拟合--FitLine()函数详解 2019-03-06
- C 存储类 2018-12-04
- 3、ObjectARX开发创建直线、圆、圆弧和修改对象属性 2018-10-08
- DIV布局之道一:DIV块的水平并排、垂直并排 2018-06-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash