# 水平可见直线 bzoj 1007

2017-01-03 19:14:15来源:cnblogs.com作者:LoseYourTemper人点击

【问题描述】

L1:y=x; L2:y=-x; L3:y=0

【输入格式】

【输出格式】

【样例输入】

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 shape26 {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 }`