 /**//*
題意: 一座房子的坐標為 (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
搜索
最新評論

|
|