poj 2074 Line of Sight (计算几何，细节题)

Line of Sight

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 3935		Accepted: 1229

Description

An architect is very proud of his new home and wants to be sure it can be seen by people passing by his property line along the street. The property contains various trees, shrubs, hedges, and other obstructions that may block the view. For the purpose of this problem, model the house, property line, and obstructions as straight lines parallel to the x axis: 

To satisfy the architect's need to know how visible the house is, you must write a program that accepts as input the locations of the house, property line, and surrounding obstructions and calculates the longest continuous portion of the property line from which the entire house can be seen, with no part blocked by any obstruction.

Input

Because each object is a line, it is represented in the input file with a left and right x coordinate followed by a single y coordinate: 
< x1 > < x2 > < y > 
Where x1, x2, and y are non-negative real numbers. x1 < x2 
An input file can describe the architecture and landscape of multiple houses. For each house, the first line will have the coordinates of the house. The second line will contain the coordinates of the property line. The third line will have a single integer that represents the number of obstructions, and the following lines will have the coordinates of the obstructions, one per line. 
Following the final house, a line "0 0 0" will end the file. 
For each house, the house will be above the property line (house y > property line y). No obstruction will overlap with the house or property line, e.g. if obstacle y = house y, you are guaranteed the entire range obstacle[x1, x2] does not intersect with house[x1, x2].

Output

For each house, your program should print a line containing the length of the longest continuous segment of the property line from which the entire house can be to a precision of 2 decimal places. If there is no section of the property line where the entire house can be seen, print "No View".

Sample Input

2 6 6
0 15 0
3
1 2 1
3 4 1
12 13 1
1 5 5
0 10 0
1
0 15 1
0 0 0

Sample Output

8.80
No View

Source

Mid-Atlantic 2004

 

终于A了。

细节比较多。

这题的大致思路是，先将结构体按照x2排序

然后从左往右扫，求得在li上的两点p1,p2 分别使得 p1.x  li[i].x2 house.x1 和 p2.x li[i+1].x1 house.x2三点共线。

然后取(p2.x-p1.x)最大的一组。

不过细节比较多。

 

说下这题需要注意的地方吧：

1. 只说了房子一定在line上面，而障碍物是可能不在房子和线之间的。如果障碍物在房子以上或者线以下就跳过（包括相等）
2. 第一个点和最后一个点要特殊处理。因为第一个的p1左边到li.x1和 第二个点的p2右边到li.x2都是有解的范围。
3. 可能没有障碍物（n==0），此时答案为li.x2-li.x1
4. 可能有障碍物，但是障碍物没起作用，就是说障碍物没有挡住任何视线，此时答案同上。所以3,4点可以和在一起考虑。可以用一个boolean变量beblocked记录是否有被遮挡的情况。如果最后发现没有遮挡的情况，那么答案为li.x2-li.x1;
5. 求得到的p1,p2点可能不在line上，要注意维护下边界。
6. 以上的情况，对于第二点中提及的特殊处理中。。也不要漏写。

/*************************************************************************
    > File Name: code/poj/2074.cpp
    > Author: 111qqz
    > Email: rkz2013@126.com 
    > Created Time: 2015年11月08日 星期日 10时26分28秒
 ************************************************************************/

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<stack>
#include<cctype>
#define fst first              
#define sec second      
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N=1E4+6;
int n;

int dblcmp(double d)
{
    return d<-eps ?-1:d>eps;
}
struct node
{
    double x1,x2,y;
}obs[N],house,li;

struct point
{
    double x,y;
};

bool cmp (node a,node b )
{
    return a.x2<b.x2;
}

int main()
{
  #ifndef  ONLINE_JUDGE 
   freopen("in.txt","r",stdin);
  #endif

   while (scanf("%lf %lf %lf",&house.x1,&house.x2,&house.y)!=EOF)
    {
    if (dblcmp(house.x1)==0&&dblcmp(house.x2)==0&&dblcmp(house.y)==0) break;
    scanf("%lf %lf %lf",&li.x1,&li.x2,&li.y);
    scanf("%d",&n);
    for ( int i = 0 ; i < n ; i++ ) scanf("%lf %lf %lf",&obs[i].x1,&obs[i].x2,&obs[i].y);

    sort(obs,obs+n,cmp);
    double sum = -1 ;
    
    point p1,p2;
    double k;
    bool beblocked = false;
        for ( int i = 0 ;i <n-1 ; i++)   //最后一个只算右端点就行      
    {
        if (dblcmp(obs[i].y-house.y)>=0||dblcmp(obs[i].y-li.y)<=0) continue;
        else beblocked = true;
        if (dblcmp(obs[i].x2-obs[i+1].x1)<0)
        {                                                                                                   
        if (dblcmp(obs[i].x2-house.x1)==0)
        {
            p1.x=house.x1; 
        }
        else
        {
            k = (house.y-obs[i].y)*1.0/(house.x1-obs[i].x2);
            p1.x = house.x1-(house.y-li.y)/k;

        }
        if (dblcmp(obs[i+1].x1-house.x2)==0)
        {
            p2.x=house.x2;
        }
        else
        {
            k = (house.y-obs[i+1].y)*1.0/(house.x2-obs[i+1].x1);
            p2.x = house.x2-(house.y-li.y)/k;
        }
        p1.x = max(p1.x,li.x1);  //边界维护
        p2.x = min(p2.x,li.x2);
//        cout<<"p1.x:"<<p1.x<<" p2.x"<<p2.x<<endl;
        if (dblcmp(p2.x-p1.x)>0)  //求连续的最大段。。。不是求和。。认真读题。
        {
            sum = max(sum,p2.x-p1.x);
            beblocked  = true;
//            cout<<"sum:"<<sum<<endl;
        }                                             
        }
    }
    //最后一个特殊处理：
    if (dblcmp(house.x1-obs[n-1].x2)==0)
    {
        p1.x = house.x1;
    }
    else
    {
        k = (house.y-obs[n-1].y)/(house.x1-obs[n-1].x2);
        p1.x = house.x1-house.y/k;
//        cout<<"k:"<<k<<endl;
    }
//    cout<<"p1.x:"<<p1.x<<" li.x2:"<<li.x2<<" minus:"<<li.x2-p1.x<<endl;
    if (dblcmp(house.y-obs[n-1].y)>0&&dblcmp(li.y-obs[n-1].y)<0)
        sum = max(sum,li.x2-p1.x),beblocked = true;

    //第一个要要单独处理
        
    if (dblcmp(house.x2-obs[0].x1)==0)
    {
        p1.x=house.x2;
    }
    else
    {
        k = (house.y-obs[0].y)/(house.x2-obs[0].x1);
        p1.x = house.x2-house.y/k;
//        cout<<"k:"<<k<<endl;
    }
    if (dblcmp(house.y-obs[0].y)>0&&dblcmp(li.y-obs[0].y)<0)
        sum = max(sum,p1.x-li.x1),beblocked = true;
        
    if (!beblocked)
    {
        sum = li.x2-li.x1;
    }
    if (dblcmp(sum)>0)
    {
        printf("%.2f
",sum);
    }
    else
    {
        puts("No View");
    }
        


    }
 #ifndef ONLINE_JUDGE  
  #endif
  fclose(stdin);
    return 0;
}