poj2074（求直线的交点）

题目链接：https://vjudge.net/problem/POJ-2074

题意：给定L1（Housing Line），L2（properity line），和一些L[i]（obstructions line），求L2最长连续区间，使得在该区间能够完整地看见L1（视线不被L[i]遮挡）。

思路：

　　简单几何题。对L[i]，计算其遮挡的区间，假设Line( L1.e , L[i].s )和L2交点的横坐标为t1,Line( L1.s , L[i].e )和L2交点的横坐标为t2，那么L[i]遮挡的区间即为[t1,t2]，求出所有的遮挡区间后按x坐标排序，遍历一遍求出最长未遮挡区间即可。

AC code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;

const double eps=1e-8;
const double inf=1e20;
int sgn(double x){
    if(abs(x)<eps) return 0;
    if(x<0) return -1;
    return 1;
}

struct Point{
    double x,y;
    Point(){}
    Point(double xx,double yy):x(xx),y(yy){}
    Point operator + (const Point& b)const{
        return Point(x+b.x,y+b.y);
    }
    Point operator - (const Point& b)const{
        return Point(x-b.x,y-b.y);
    }
    double operator * (const Point& b)const{
        return x*b.x+y*b.y;
    }
    double operator ^ (const Point& b)const{
        return x*b.y-b.x*y;
    }
    //绕原点旋转角度b（弧度值），后x、y的变化
    void transXY(double b){
        double tx=x,ty=y;
        x=tx*cos(b)-ty*sin(b);
        y=tx*sin(b)+ty*cos(b);
    }
};

struct Line{
    Point s,e;
    Line(){}
    Line(Point ss,Point ee){
        s=ss,e=ee;
    }
    //两直线相交求交点
    //第一个值为0表示直线重合，为1表示平行，为2表示相交
    //只有第一个值为2时，交点才有意义
    pair<int,Point> operator &(const Line &b)const{
        Point res = s;
        if(sgn((s-e)^(b.s-b.e)) == 0)
        {
            if(sgn((s-b.e)^(b.s-b.e)) == 0)
                return make_pair(0,res);//重合
            else return make_pair(1,res);//平行
        }
        double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));
        res.x += (e.x-s.x)*t;
        res.y += (e.y-s.y)*t;
        return make_pair(2,res);
    }
};

double dis(Point a,Point b){
    return sqrt((b-a)*(b-a));
}

typedef pair<double,double> PDD;
const int maxn=1005;
Line L[maxn],L1,L2;
double x1,x2,y,ans;
int n,cnt,cnt2;
PDD pdd[maxn];

bool cmp(PDD p1,PDD p2){
    if(p1.first==p2.first)
        return p1.second<p2.second;
    return p1.first<p2.first;
}

int main(){
    while(scanf("%lf%lf%lf",&x1,&x2,&y),sgn(x1)||sgn(x2)||sgn(y)){
        L1.s.x=x1,L1.e.x=x2,L1.s.y=L1.e.y=y;
        scanf("%lf%lf%lf",&x1,&x2,&y);
        L2.s.x=x1,L2.e.x=x2,L2.s.y=L2.e.y=y;
        scanf("%d",&n);
        cnt=cnt2=0;
        for(int i=0;i<n;++i){
            scanf("%lf%lf%lf",&x1,&x2,&y);
            if(y>=L1.s.y||y<=L2.s.y) continue;
            L[++cnt].s.x=x1,L[cnt].e.x=x2,L[cnt].s.y=L[cnt].e.y=y;
        }
        for(int i=1;i<=cnt;++i){
            double t1=(L2&(Line(L1.e,L[i].s))).second.x;
            double t2=(L2&(Line(L1.s,L[i].e))).second.x;
            if(t2<L2.s.x||t1>L2.e.x) continue;
            if(t1<L2.s.x) t1=L2.s.x;
            if(t2>L2.e.x) t2=L2.e.x;
            pdd[++cnt2].first=t1,pdd[cnt2].second=t2;
        }
        sort(pdd+1,pdd+cnt2+1,cmp);
        ans=L2.e.x-pdd[cnt2].second;
        double t1=L2.s.x;
        int j=1;
        while(1){
            while(pdd[j].first<t1){
                t1=max(t1,pdd[j].second);
                ++j;
            }
            if(j>cnt2) break;
            if(pdd[j].first>=t1){
                ans=max(ans,pdd[j].first-t1);
                t1=pdd[j].second;
                ++j;
            }
            if(j>cnt2) break;
        }
        if(sgn(ans)!=0)
            printf("%.2f
",ans);
        else
            printf("No View
");
    }
}

相关推荐