【BZOJ1007】水平可见直线

Zarxdy34 posted @ 2015年9月28日 11:13 in BZOJ with tags 凸包 , 315 阅读

  把直线按照斜率排序,所有的可见线段画出来是个凸包。

 

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=50010;
const double eps=1e-10;
 
struct Line
{
    double a,b;
    int ID;
    bool operator < (const Line &p) const {return a<p.a || (abs(a-p.a)<eps && b>p.b);}
}L[maxn];
typedef Line Node;
double GetX(Line x,Line y) {return (y.b-x.b)/(x.a-y.a);}
 
int Q[maxn],top;
int I[maxn];
double D[maxn];
int n;
 
int main()
{
    scanf("%d",&n);
    for (int i=0;i<n;i++) scanf("%lf%lf",&L[i].a,&L[i].b),L[i].ID=i+1;
    sort(L,L+n);
    Q[top]=0;D[top]=-1e80;
    for (int i=1;i<n;i++)
    {
        if (abs(L[i].a-L[Q[top]].a)<eps) continue;
        D[++top]=GetX(L[i],L[Q[top-1]]);
        while (D[top]-D[top-1]<eps) D[--top]=GetX(L[i],L[Q[top-1]]);
        Q[top]=i;
    }
    for (int i=0;i<=top;i++) I[L[Q[i]].ID]=1;
    for (int i=1;i<=n;i++) if (I[i]) printf("%d ",i);
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Copyright © 2007

Webdesign, tvorba www stránek

Valid XHTML 1.1