题目链接：http://poj.org/problem?id=1556
————————————————————————————————————————————————————
题目简述：如图中所示，已知起点和终点，中间有墙挡住，问最短的路是多长
————————————————————————————————————————————————————
解题思路：看别人的解题报告是用图+dijkstra做的。我没有用图论的方法，直接做的。
我的思路是，读入各点，按顺序存进p数组（p是个结构体，其中用了重载），因为每个x坐标就对应着4个点，所以不需要做标记，有寻址公式就行。
然后将x的坐标按顺序存到xs数组中。然后开始对各个点，按顺序扫描，如果和起点之间无障碍物，则该点的len就是到起点的距离。如果有障碍物，就
从p[0]点开始一个一个的扫描，如果与p[j]点之间没有障碍物，则计算出到该点距离加上该点的len。想法是很裸的（这个词刚刚学会），而且话说其实
应该把起点也放入p 数组中，这样不需要分情况讨论了，代码会更加简洁，不修改了。
其中对于障碍物的判断方法，我是这样做的： 如果我们当前状态是i，待检测的点是j，我们可以用点斜式列出过点i和点j的方程。将i和j之间的墙们的横坐标带进
方程（xs就用上了，再加上一个寻址公式），求出一个纵坐标，再考查纵坐标是否在墙上，就可以了。思路挺简单，不过写起来有点麻烦，寻址公式要特别小心。
————————————————————————————————————————————————————
题目小结：
一开始没有ac，遇到的问题多由粗心所致：
1、bst求出来之后，忘记赋值给p[i].len ( = = 这么傻的问题都能犯啊)。。。。
2、寻址公式写错了个地方。
另外，在写重载的时候，一开始没有编译通过，问题如下：
3、重载时重载函数要与结构体名一致。
————————————————————————————————————————————————————
待解问题：
1、重载时需要加入一行 Line(){}；
否则会报错 |error: no matching function for call to 'Line::Line()'|，不知为何
2、由于符号重载时多加了个 &，故报warning: reference to local variable 'c' returned|
下学期就该学c++，大概到时候就明白了吧，先搁着！
————————————————————————————————————————————————————
源代码，其中判断相交的函数没用上，算作下次的模板。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
using namespace std;
typedef float T;
struct Pt
{
T x;
T y;
T len;
Pt(){}
Pt(T px,T py)
{
x = px;
y = py;
}
Pt &operator +(const Pt &p) const
{
Pt c;
c.x = x + p.x;
c.y = y + p.y;
return c;
}
Pt &operator -(const Pt &p) const
{
Pt c;
c.x = x - p.x;
c.y = y - p.y;
return c;
}
};
struct Line
{
Pt a;
Pt b;
int cont;
Line(){}
Line (Pt p1,Pt p2)
{
a = p1;
b = p2;
}
}line[1010];
T dpr(Pt a,Pt b,Pt c) //µã»ý
{
return (b.x-a.x)*(c.x-a.x)+(b.y-a.y)*(c.y-a.y);
}
T cpr(Pt a,Pt b,Pt c) //ab * ac
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(Line l1,Line l2)
{
return l1.a.x < l2.a.x;
}
T min(T a,T b)
{
if(a>b) return b;
else return a;
}
bool segments_intersect(Pt p1,Pt p2,Pt p3,Pt p4) //严格相交，即交在端点不算相交,不需要判断交点位置，相交时返回1。本题亦不会出现点在线段上的问题
{
float d1,d2,d3,d4;
d1 = cpr(p1,p3,p4);
d2 = cpr(p2,p3,p4);
d3 = cpr(p3,p1,p2);
d4 = cpr(p4,p1,p2);
if(d1*d2<0 && d3*d4<0)
return 1;
else
return 0;
}
Pt p[100],p0,pn;
int k = 0,m = 0;
float xs[100];
bool segments(Pt a,Pt b,int i,int j) //求与各个x的交点
{
int k = 0,t = 0;
T y = 0;
for(k = i/4+1;k<j/4+1;k++)
{
y = a.y + (b.y - a.y)*(xs[k] - a.x)/(b.x-a.x);
if(y < p[(k-1)*4].y || (y<p[(k-1)*4+2].y && y>p[(k-1)*4+1].y) || y>p[(4*k-1)].y )
return 1;
}
return 0;
}
T d(Pt a,Pt b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main()
{
int n = 0,i = 0,j = 0;
T x = 0,y = 0;
float bst = 0;
unsigned temp = 0;
p0 = Pt(0,5);
pn = Pt(10,5);
while((scanf("%d",&n),n)!=-1)
{
k = 0;
m = 1;
xs[0] = 0;
for(i = 0;i<n;i++)
{
scanf("%f",&x);
xs[m++] = x;
for(j = 0;j<4;j++)
{
scanf("%f",&y);
p[k++] = Pt(x,y);
}
}
if(!segments(p0,pn,0,k))
{
pn.len = d(pn,p0);
printf("%.2f\n",pn.len);
continue;
}
for(i = 0;i<k;i++)
{
bst = (~temp)>>1;
if(i/4 == 0)
p[i].len = d(p[i],p0);
else
{
if(!segments(p[i],p0,0,i))
{
p[i].len = d(p[i],p0);
continue;
}
for(j = 0;j<=(i/4)*4-1;j++)
{
if(!segments(p[i],p[j],j,i))
if(d(p[i],p[j])+p[j].len<bst)
bst = d(p[i],p[j])+p[j].len;
}
p[i].len = bst;
}
}
bst = (~temp)>>1;
for(i = 0;i<k;i++)
{
if(!segments(p[i],pn,i,k))
if(d(p[i],pn)+p[i].len<bst)
bst = d(p[i],pn)+p[i].len;
}
printf("%.2f\n",bst);
}
return 0;
}