POJ 2074 线段相交 视线问题

  1. 云栖社区>
  2. 博客列表>
  3. 正文

POJ 2074 线段相交 视线问题

prime7 2013-04-15 15:43:00 浏览352 评论0

摘要: 题意:给你一个代表房子的线段,代表路的线段,然后代表各种障碍物的线段。求出路上最长的区间,在区间中能看到完整的房子。 首先筛选出纵坐标在房子与路之间的,再根据视线完全能看到就行了。 #include <iostream> #include<cstdio> #include<cstring> #...

题意:给你一个代表房子的线段,代表路的线段,然后代表各种障碍物的线段。求出路上最长的区间,在区间中能看到完整的房子。

首先筛选出纵坐标在房子与路之间的,再根据视线完全能看到就行了。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef double PointType;
struct point
{
    PointType x,y;
};
struct line
{
    point l,r;
};
line house,road,data[200],ans[200];
int ansnum,n,num;
void getcoor(line &ans,double x1,double x2,double y)  //构建点坐标
{
    ans.l.x=x1,ans.r.x=x2;
    ans.l.y=ans.r.y=y;
}
point getpoint(point a,point b)   //求在路上的交点
{
    point wans;
    double k,b1;
    if(a.x==b.x)
        wans.x=a.x;
    else
        k=(a.y-b.y)/(a.x-b.x),
          b1=a.y-k*a.x,
             wans.x=(road.l.y-b1)/k;
    wans.y=road.l.y;
    return wans;
}
void getans(line a)  //将路上不可视区域转化成线段
{
    ans[ansnum].l=getpoint(a.l,house.r);
    ans[ansnum].r=getpoint(a.r,house.l);
    ansnum++;
}
int cmp(line a,line b)
{
    return a.l.x<b.l.x;
}
int main()
{
    double x1,x2,y;
    while(~scanf("%lf%lf%lf",&x1,&x2,&y),(x1||x2||y))
    {
        num=ansnum=0;
        getcoor(house,x1,x2,y);
        scanf("%lf%lf%lf",&x1,&x2,&y),getcoor(road,x1,x2,y);
        scanf("%d",&n);
        for(int i=0; i<n; i++)
        {
            scanf("%lf%lf%lf",&x1,&x2,&y);
            if(y<house.l.y&&y>=road.l.y) //筛选线段在房子和路之间的障碍物
                getcoor(data[num++],x1,x2,y),getans(data[num-1]);
        }
        if(n==0)
        {
            printf("%.2f\n",road.r.x-road.l.x);
            continue;
        }
        getcoor(ans[ansnum++],-9999999,road.l.x,road.l.y);
        getcoor(ans[ansnum++],road.r.x,9999999,road.l.y);
        sort(ans,ans+ansnum,cmp);
        double ansmax=0,bj=ans[0].r.x;
        for(int i=0; i<ansnum; i++)
        {
            if(ans[i].l.x>bj)
                ansmax=max(ansmax,ans[i].l.x-bj);
            bj=max(ans[i].r.x,bj);
        }
        if(ansmax==0)
            puts("No View");
        else
            printf("%.2f\n",ansmax);
    }
    return 0;
}




用云栖社区APP,舒服~

【云栖快讯】诚邀你用自己的技术能力来用心回答每一个问题,通过回答传承技术知识、经验、心得,问答专家期待你加入!  详情请点击

网友评论

prime7
文章209篇 | 关注0
关注
移动测试(Mobile Testing)是为广大企业客户和移动开发者提供真机测试服务的云平台... 查看详情
阿里云数据库内置的智能专家,提供云数据库问题诊断、性能优化、SQL分析、资源分析、优化报告等... 查看详情
通过机器学习和数据建模发现潜在的入侵和攻击威胁,帮助客户建设自己的安全监控和防御体系,从而解... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
阿里云总监课正式启航

阿里云总监课正式启航