565
技術社區[雲棲]
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;
}
最後更新：2017-04-03 20:43:08