/**//* 题意: 一座房子的坐标为 (x1,y) (x2,y) 其下面有一些障碍物,问在线段(x1',y)(x2',y)能看到整座房子的最大连续的长度 我用比较暴力的方法 枚举房子左端点跟障碍物的右端点连成的直线leftView,然后找出房子右端点跟障碍物的 左端点的连线中rightView最接近leftView, 则这个区域内就是可见的了,更新答案
细节较多 参考数据: http://poj.org/showmessage?message_id=67499 */
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath>
using namespace std;
const int MAXN = 110; const double EPS = 1e-8;
inline double fix_double(double x) { return fabs(x)<EPS ? 0.0 : x; }
inline int sign(double x) { return x<-EPS?-1:x>EPS; }
//这里只在构造时fix_double //其他地方,如加法、减法 可能也需要修正一下 //那个构造直线时,INF不要开得太多的话一般没问题的 struct Point { double x,y; Point(){} Point(double _x , double _y) { x = fix_double(_x); y = fix_double(_y); } bool operator == (const Point B)const { return sign(x-B.x)==0 && sign(y-B.y)==0; } Point operator - (const Point B)const { return Point(x-B.x , y-B.y); } };
//这里没考虑线段、直线 退化成点的情况 struct Segment { Point a,b; Segment(){} Segment(Point _a,Point _b) { a = _a; b = _b; } };
struct Line { Point a,b; double ia , ib , ic;//iax + iby + ic = 0 Line(){} Line(Point _a , Point _b) { a = _a; b = _b; } void make()//(y2-y1)x - (x2-x1)y + x2y1 - x1y2 = 0 { ia = b.y - a.y; ib = a.x - b.x; ic = b.x*a.y - a.x*b.y; //if(sign(ia)<0)ia = -ia , ib = -ib , ic = -ic; } };
//OA*OB = |OA|*|OB|*cos(AOB) inline double dot(Point O , Point A , Point B) { Point OA = A - O; Point OB = B - O; return OA.x * OB.x + OA.y * OB.y; }
//OA×OB = |OA|*|OB|*sin(AOB) //>0 OB在OA的逆时针方向(右手螺旋) //=0 OB跟OA共线 inline double cross(Point O , Point A , Point B) { Point OA = A - O; Point OB = B - O; return OA.x * OB.y - OB.x * OA.y; }
//判断一个点是否在线段(包括端点)上 : 向量共线 , 点位于线段之间 //0 不在 1在线段内 2在端点处 int inSegment(Point pt , Segment seg) { if(sign(cross(pt,seg.a, seg.b)))return 0; int ans = sign(dot(pt , seg.a , seg.b)); return ans == 0 ? 2 : ans < 0; }
//线段和线段相交情况: 0:不相交, 1:规范相交, 2:交于端点 , 3:有重合部分 int across(Segment AB, Segment CD)//快速排斥实验 + 相互跨立(是相互) { if( max(AB.a.x , AB.b.x) < min(CD.a.x , CD.b.x) || max(AB.a.y , AB.b.y) < min(CD.a.y , CD.b.y) || max(CD.a.x , CD.b.x) < min(AB.a.x , AB.b.x) || max(CD.a.y , CD.b.y) < min(AB.a.y , AB.b.y) ) return 0; int AB_CD = sign(cross(AB.a , AB.b , CD.a)) * sign(cross(AB.a , AB.b , CD.b)); int CD_AB = sign(cross(CD.a , CD.b , AB.a)) * sign(cross(CD.a , CD.b , AB.b));
//有重合部分 if(AB_CD == 0 && CD_AB == 0 && (inSegment(AB.a , CD) == 1 || inSegment(AB.b , CD) == 1 ) )return 3;
if(AB_CD < 0)//CD跨立AB { return CD_AB ==0 ? 2: CD_AB < 0; } else if(AB_CD == 0)return CD_AB <= 0 ? 2 : 0; return 0; }
//线段和直线相交情况: 0:不相交, 1:规范相交, 2:不规范相交(交于端点或重合) int across(Segment seg, Line line)//判断线段与直线相交 只需判断线段是否跨立直线即可 { int ans = sign(cross(line.a,line.b,seg.a)) * sign(cross(line.a,line.b,seg.b)); return ans == 0 ? 2 : ans < 0; }
//直线和直线相交情况: 0:不相交(平行), 1:规范相交, 2:不规范相交(重合) int across(Line AB , Line CD) { if( sign(cross(Point(0,0) , AB.b-AB.a , CD.b-CD.a )) )return 1; return sign(cross(AB.a , AB.b , CD.a )) == 0? 2 : 0; }
//计算交点前需先判断是否相交 直线可以是平行于y轴的 Point intersect(Line LA , Line LB) { LA.make(); LB.make(); double a1 = LA.ia , b1 = LA.ib , c1 = LA.ic; double a2 = LB.ia , b2 = LB.ib , c2 = LB.ic; double x = (c1*b2 - b1*c2)/(a2*b1-a1*b2); double y; if(sign(b1)) y = -(a1*x + c1)/b1; else y = -(a2*x + c2)/b2; return Point(x,y); }
Point intersect(Segment SA , Segment SB) { if(SA.a == SB.a || SA.a == SB.b)return SA.a; if(SA.b == SB.a || SA.b == SB.b)return SA.b; double AB_C = cross(SA.a, SA.b, SB.a); double AB_D = cross(SA.a, SA.b, SB.b); double x = (AB_D * SB.a.x - AB_C * SB.b.x) / (AB_D - AB_C); double y = (AB_D * SB.a.y - AB_C * SB.b.y) / (AB_D - AB_C); return Point(x,y); }
Point intersect(Segment seg , Line line) { Line _line = Line(seg.a , seg.b); return intersect(_line,line); }
Segment home , propertySeg , obstruction[MAXN]; int n;
bool chkView( Line view ) { for(int i = 0; i < n ;i ++) { if( across(obstruction[i] , view) == 1 )return false; } return true; }
int main() {
#ifdef ONLINE_JUDGE #else freopen("in","r",stdin); #endif while( scanf("%lf%lf%lf" , &home.a.x, &home.b.x , &home.a.y) ) { home.b.y = home.a.y; if( sign(home.a.x)==0 && sign(home.b.x)==0 && sign(home.a.y)==0 ) break;
scanf("%lf%lf%lf" , &propertySeg.a.x, &propertySeg.b.x , &propertySeg.a.y); propertySeg.b.y = propertySeg.a.y;
Line propertyLine = Line(propertySeg.a , propertySeg.b);
scanf("%d",&n); int _n = 0; for(int i = 0 ; i < n ; i++)//先去掉一些不可能的 { scanf("%lf%lf%lf" , &obstruction[_n].a.x , &obstruction[_n].b.x , &obstruction[_n].a.y); obstruction[_n].b.y = obstruction[_n].a.y; if(sign(obstruction[_n].a.y - home.a.y) < 0 && sign(obstruction[_n].a.y - propertySeg.a.y) > 0) _n++; } n = _n; double ans = 0.0; for(int i = 0 ; i < n; i++) { Line leftView = Line(home.a , obstruction[i].b) , rightView; if( across(propertySeg , leftView) == 0 || !chkView(leftView) )continue; Point leftPt = intersect(propertySeg , leftView) , rightPt; bool flag = false; //check for propertySeg.b rightPt = propertySeg.b; rightView = Line(home.b , rightPt);
if(chkView(rightView))flag = true; for(int j = 0; j < n; j++) { if(sign(cross(home.a , leftPt , obstruction[j].a)) > 0 ) { rightView = Line(home.b , obstruction[j].a); if(!chkView(rightView) )continue; Point pt = intersect(propertyLine , rightView); if(flag == false || rightPt.x > pt.x ) rightPt = pt; flag = true; } } if(flag) ans = max(ans , rightPt.x - leftPt.x); }
//check for propertySeg.a { Line leftView = Line(home.a , propertySeg.a) , rightView; if( chkView(leftView) ) { Point leftPt = propertySeg.a , rightPt; bool flag = false; //check for propertySeg.b rightPt = propertySeg.b; rightView = Line(home.b , rightPt); if(chkView(rightView))flag = true; for(int j = 0; j < n; j++) { if(sign(cross(home.a , leftPt , obstruction[j].a)) > 0 ) { rightView = Line(home.b , obstruction[j].a); if(!chkView(rightView) )continue; Point pt = intersect(propertyLine , rightView); if(flag == false || rightPt.x > pt.x ) rightPt = pt; flag = true; } } if(flag) ans = max(ans , rightPt.x - leftPt.x); } }
if(sign(ans) == 0 ) puts("No View"); else printf("%.2f\n" , ans ); } return 0; }
|
|
常用链接
随笔分类
Links
搜索
最新评论
|
|