电子商务网站建设项目的阶段的划分,红色简约的手机社区类网站html5响应式模板下载,wordpress登录入口链接,海口建站网站模板Description 在xoy直角坐标平面上有n条直线L1,L2,...Ln,若在y值为正无穷大处往下看,能见到Li的某个子线段,则称Li为可见的,否则Li为被覆盖的. 例如,对于直线:L1:yx; L2:y-x; L3:y0 则L1和L2是可见的,L3是被覆盖的. 给出n条直线,表示成yAxB的形式(|A|,|B|500000),且n条直线两… Description 在xoy直角坐标平面上有n条直线L1,L2,...Ln,若在y值为正无穷大处往下看,能见到Li的某个子线段,则称Li为可见的,否则Li为被覆盖的. 例如,对于直线:L1:yx; L2:y-x; L3:y0 则L1和L2是可见的,L3是被覆盖的. 给出n条直线,表示成yAxB的形式(|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 Solution 按斜率从小到大给直线排序维护一个下凸壳 要把新加的线与凸壳的交点以右的直线删掉因为新加的线一定在它与它之前的线组成的凸壳中 1 #include bits/stdc.h2 using namespace std;3 const double EPS 1e-8;4 struct line5 {6 int id;7 double k, b;8 bool operator (const line rhs) const9 {
10 return fabs(k - rhs.k) EPS ? b rhs.b : k rhs.k;
11 }
12 }a[100005];
13 int sta[100005], ans[100005];
14
15 double getx(int x)
16 {
17 return (a[sta[x]].b - a[sta[x - 1]].b) / (a[sta[x - 1]].k - a[sta[x]].k);
18 }
19
20 int main()
21 {
22 int n, top;
23 cin n;
24 for(int i 1; i n; i)
25 {
26 cin a[i].k a[i].b;
27 a[i].id i;
28 }
29 sort(a 1, a n 1);
30 sta[top 1] 1;
31 for(int i 2; i n; i)
32 {
33 sta[top] i;
34 while(top 1)
35 if(fabs(a[i].k - a[sta[top - 1]].k) EPS) sta[--top] i;
36 else if(top 2 getx(top) - getx(top - 1) EPS)
37 sta[--top] i;
38 else break;
39 }
40 for(int i 1; i top; i)
41 ans[i] a[sta[i]].id;
42 sort(ans 1, ans top 1);
43 for(int i 1; i top; i)
44 cout ans[i] ;
45 cout endl;
46 return 0;
47 } View Code 转载于:https://www.cnblogs.com/CtrlCV/p/5585497.html
