题目大意:(下面的线段都与x轴平行)给两条线段,一个点在其中一条线段看另一条线段,但是中间有很多线段阻挡视线。求在线段上最大连续区间使得在上面的点都能看见另一条线段。
——————————————
这题的思路很简单,首先根据左端点先排个序,然后找前一条线段的右端点和房子左端点连,后一条线段的左端点和房子右端点连,那么两条连线与路的交的范围即是可行解。
但是debug真的累……好在poj有神犇提供了部分debug数据,经过多次尝试,发现:
1.筛除不在路和房子之间的线段。
2.可行解区域可能超过路。
3.线段可能互相遮挡。
第三条蛮麻烦的,一个简单粗暴的比较方法就是枚举所有线段,判断是否有和线段相交,如果相交则更换为该线段的左/右端点。
#include#include #include #include #include #include #include using namespace std;typedef double dl;const int INF=2147483647;const int N=201;struct point{ //既是向量又是点 dl x; dl y;};struct line{ dl x1; dl x2; dl y;}p[N],st,ed;bool cmp(line a,line b){ return (a.x1 =1;i--){ if(p[i].y>st.y||p[i].y st.y||p[i].y st.y||p[j].y st.y||p[j].y ed.x2)r=ed.x2; maxn=max(maxn,r-l); } } if(maxn==0){ puts("No View"); }else{ printf("%.2f\n",maxn); } } return 0;}