POJ 2074 线段相交 视线问题

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

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

#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;
}
时间: 2024-12-08 11:28:50

POJ 2074 线段相交 视线问题的相关文章

POJ 1556 线段相交+最短路

题意:给出一个房间的俯视图 求从(0,5)到(10,5)的最短路径. 求出没有墙挡住的两点距离再用弗洛伊德求出0-sum的最短路径就可以.需要注意最短路可能经过某墙的端点,这时候不能判断条路径为非法. #include <iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; typedef doub

POJ 2653 暴力判断线段相交

题意是按照输入的先后顺序放木棍,然后输出最上层的木棍,何为最上层,就是木棍上方没有木棍和它相交就行. 这题坑爹啊,一直TLE后来才发现最上层木棍不是底下的木棍数最多而是只要上方没有木棍就行.所以只需要开一个标记数组从前往后如果后面有与它相交的那么这个木棍肯定不是最上层的,知道这些再知道线段相交的模板就可以A了. #include <iostream> #include<cstdio> #include<cstring> #include<algorithm>

POJ 1066 判断线段相交

题意:有个考古队进金字塔里盗墓,大小100*100,样图是一个俯视图,给了财宝坐标,又给了各个墙.题目规定考古队在每面墙的中点处开一个洞,这样就避免了两墙交点的情况,求最小的凿墙数目. 很明显,枚举连接四面两个墙之间中点与宝藏的线段,求出这种线段与墓里墙相交的最小值.其实可以不用枚举中点,直接用墙的端点与宝藏相连的线段就行,细想一想可以想明白. #include <iostream> #include<cstdio> #include<cstring> #include

POJ 3304 判断直线与线段相交

题意:问存不存在一条直线,各个线段在直线上的投影有公共部分,也就是判断是否存在一条直线将所有线段都相交. 枚举所有端点构成的直线如果有一条直线相交所有线段那么就存在. #include <iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define eps 1e-8 typedef doub

POJ 3468 线段树 区间更新区间查询

题意:给出一段数列,任意区间加上一个整数v,任意区间查询.给出N个数,Q次操作. 线段树的题,延迟指针不更新到底就行了. #include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn 100005 long long sum[maxn<<2],col[maxn<<2]; void

【转】POJ 3264 线段树解法

每个算法都是数学家或者计算机学家多年研究的结果,不是我自己臆造的,所以学习一个新算法的最佳方法还是看写的好的代码. 按照惯例,我就粘贴一个网上写的很好的帖子... 原文地址:http://ip96cns.blog.163.com/blog/static/17009519220112525029459/ 线段树的查找:(感谢高手指点,虽然只是一点却让我把线段树的内容理顺了)这里是我的一些总结吧           一个线段树的结点表示一个区间,同时结点中保存所需要的信息.          如果询

POJ 2653 Pick-up sticks:计算几何 求线段交点

POJ 2653:http://poj.org/problem?id=2653 题意:题意很简单,就是在地上按顺序撒一对木棒,看最后有多少是被压住的,输出没有被压住的木棒的序号.有点坑的就是没说清楚木棒怎么算压住,也不知道是不是规范相交...我就判断了一下包括端点重合跟部分相交的. 思路:一开始我想的是从后往前遍历,找到每一条边,看他是不是压到之前的边了,如果压到了,就把之前的变标记一下,最后统计没被标记过的,但是TLE了...就只能从前面开始找,遍历每一条边是否被后面的压过了,压过了就直接br

POJ题目分类

初期: 一.基本算法:      (1)枚举. (poj1753,poj2965)      (2)贪心(poj1328,poj2109,poj2586)      (3)递归和分治法.      (4)递推.      (5)构造法.(poj3295)      (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法:      (1)图的深度优先遍历和广度优先遍历.      (2)最短路径算法(dijkstra,bellman-ford

poj分类

初期: 一.基本算法:      (1)枚举. (poj1753,poj2965)      (2)贪心(poj1328,poj2109,poj2586)      (3)递归和分治法.      (4)递推.      (5)构造法.(poj3295)      (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法:      (1)图的深度优先遍历和广度优先遍历.      (2)最短路径算法(dijkstra,bellman-ford