BZOJ 1007(水平可见直线-斜率排序+栈贪心)

1007: [HNOI2008]水平可见直线
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 1830 Solved: 656
[Submit][Status][Discuss]
Description

Input
第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi

Output
从小到大输出可见直线的编号，两两中间用空格隔开,最后一个数字后面也必须有个空格

Sample Input
3
-1 0
1 0
0 0

Sample Output
1 2

按斜率排序，从小到大插入。
半平面交的特殊情况：
每次
都要保证x坐标<x,top>><top,top'> 否则top不可见（top为栈顶元素）
[cpp]
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
using namespace std;
#define MAXN (50000+10)
int n;
struct line
{
    int k,b,i;
    friend bool operator<(line a,line b) {return (a.k==b.k)?a.b>b.b:a.k<b.k;   }
    friend double intx(line a,line b)
    {
        return (double)(b.b-a.b)/(a.k-b.k);
    }
}a[MAXN];
int s[MAXN],size=0;
void push(int x)
{
    while (size>1&&intx(a[s[size]],a[s[size-1]])>=intx(a[s[size]],a[x])) size--;
    s[++size]=x;
}
bool b[MAXN];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {scanf("%d%d",&a[i].k,&a[i].b);a[i].i=i;}
    sort(a+1,a+1+n);
    push(1);
    for (int i=2;i<=n;i++)
        if (a[i].k>a[i-1].k) push(i);
// for (int i=1;)
    memset(b,0,sizeof(b));for (int i=1;i<=size;i++) b[a[s[i]].i]=1;
    for (int i=1;i<=n;i++) if (b[i]) cout<<i<<' ';
    return 0;
}

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
using namespace std;
#define MAXN (50000+10)
int n;
struct line
{
int k,b,i;
friend bool operator<(line a,line b) {return (a.k==b.k)?a.b>b.b:a.k<b.k; }
friend double intx(line a,line b)
{
return (double)(b.b-a.b)/(a.k-b.k);
}
}a[MAXN];
int s[MAXN],size=0;
void push(int x)
{
while (size>1&&intx(a[s[size]],a[s[size-1]])>=intx(a[s[size]],a[x])) size--;
s[++size]=x;
}
bool b[MAXN];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) {scanf("%d%d",&a[i].k,&a[i].b);a[i].i=i;}
sort(a+1,a+1+n);
push(1);
for (int i=2;i<=n;i++)
if (a[i].k>a[i-1].k) push(i);
// for (int i=1;)
memset(b,0,sizeof(b));for (int i=1;i<=size;i++) b[a[s[i]].i]=1;
for (int i=1;i<=n;i++) if (b[i]) cout<<i<<' ';
return 0;
}

补充：软件开发 , C++ ,