【计算几何】[HNOI2008][HYSBZ/BZOJ1007]水平可见直线

题目链接

分析

如果两条直线斜率相等，显然，截距较小的那一条无论如何都不可见，删掉它们。
我们可以将剩下直线按照斜率的数值从小到大排序。
假设第i条直线是可见的，然后，我们从第i+1条开始向后枚举，分别计算这条直线（设为第j条）和第i条直线交点的横坐标，记作 xi,j 。
若

xi,k≤xi,j(j<k)

显然，第j条直线不可见，因为

{yi>yjyk>yjx≤xi,jx>xi,j

通过这样，我们可以求出在第i条直线之后可见的直线是那一条。
显然，第1条直线是可见的，最后一条直线是可见的，所以，我们从第1条直线开始求出所以可见直线的编号即可。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 50000
int n,ln;
bool f[MAXN+10];
struct node{
int a,b,pos;
bool operator<(const node &x)const{
if(x.a==a)
return b>x.b;
return a<x.a;
    }
bool operator==(const node &x)const{
return x.a==a;
    }
}a[MAXN+10],b[MAXN+10];
void Read(int &x){
char c;
bool f=0;
while(c=getchar(),c!=EOF){
if(c=='-')
            f=1;
if(c>='0'&&c<='9'){
            x=c-'0';
while(c=getchar(),c>='0'&&c<='9')
                x=x*10+c-'0';
            ungetc(c,stdin);
if(f)
                x=-x;
return;
        }
    }
}
void read(){
    Read(n);
int i;
for(i=1;i<=n;i++)
        Read(b[i].a),Read(b[i].b),b[i].pos=i;
    sort(b+1,b+n+1);
    ln=n;
    n=0;
    a[++n]=b[1];
for(i=2;i<=ln;i++)
if(!(b[i]==b[i-1]))
            a[++n]=b[i];
}
int compare(int x,int y,int a,int b){
long long t1=1ll*x*b,t2=1ll*a*y,ty=1ll*y*b;
    t1-=t2;
if(t1==0)
return 0;
if((t1>0&&ty>0)||(t1<0&&ty<0))
return 1;
return -1;
}
void solve(){
int i,x,y,tx,ty,j,ti;
for(i=1;i<n;i=ti){
        f[a[i].pos]=1;
        x=0x7fffffff,y=1;
for(j=i+1;j<=n;j++){
            tx=a[j].b-a[i].b,ty=a[i].a-a[j].a;
if(compare(tx,ty,x,y)<=0)
                x=tx,y=ty,ti=j;
        }
    }
    f[a[n].pos]=1;
}
void print(){
for(int i=1;i<=ln;i++)
if(f[i])
printf("%d ",i);
}
int main()
{
    read();
    solve();
    print();
}