【POJ-1556-The Doors】线段求交+DP
POJ-1556-The Doors
题意
一个房间内有平行的n堵墙,每个墙上有两道门,求从起点走到终点的最短路径。
例如下图:
做法
可以到某个门的最短距离一定是由某个门的两端点出发的,所以我们只要从左到右算出到达每个点的最短距离,每个点用所有之前可以直接到达这个点的点去松弛这个点,复杂度
代码
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;
const double eps = 1e-12;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 1010;
int sgn( double x)
{
if (fabs(x) <eps) return 0;
if(x <0) return -1;
return 1;
}
inline double sqr( double x)
{
return x * x;
}
struct Point
{
double x, y;
Point() {}
Point ( double _x, double _y)
{
x = _x, y = _y;
}
void input()
{
scanf("%lf%lf", &x, &y);
}
void output()
{
cout <<"x= "<<x << " y= " << y << endl;
}
bool operator == (Point b) const
{
return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
}
bool operator < (Point b) const
{
return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;
}
Point operator - (const Point &b) const
{
return Point(x - b.x, y - b.y);
}
//叉积 |a||b|sin
double operator ^ (const Point &b) const
{
return x * b.y - y * b.x;
}
//点积 |a||b|cos 向量点积之后反过来求夹角
double operator * (const Point & b) const
{
return x * b.x + y * b.y;
}
//利用库函数计算点到(0,0)的距离
double len()
{
return hypot(x, y);
}
//返回长度的平方
double len2()
{
return x * x + y * y;
}
//返回两点间距离
double distance(Point p)
{
return hypot(x - p.x, y - p.y);
}
//向量加法
Point operator + (const Point &b) const
{
return Point(x + b.x, y + b.y);
}
//向量乘常数
Point operator * (const double &k) const
{
return Point(x * k, y * k);
}
//向量除以常数
Point operator / (const double &k) const
{
return Point (x / k, y / k);
}
//求a,b以当前点为中间点的角
double rad(Point a, Point b)
{
Point p = *this;
return fabs(atan2( fabs((a - p) ^ (b - p)), (a - p) * (b - p) ));
}
//转换为长度为r的向量
Point trunc(double r)
{
double l = len();
if (!sgn(l)) return *this;
r /= l;
return Point(x * r, y * r);
}
};
struct Line
{
Point s, e;
Line() {}
Line(Point _s, Point _e)
{
s = _s, e = _e;
}
//直线判断重合
bool operator == (Line v)
{
return (s == v.s) && (e == v.e);
}
//根据一个点和倾斜角angle确定直线,0<=angle<pi
Line (Point p, double angle)
{
s = p;
if (sgn(angle - pi / 2) == 0)
e = (s + Point (0, 1));
else
e = (s + Point (1, tan(angle)));
}
//ax+by+c确定直线
Line(double a, double b, double c)
{
if (sgn(a) == 0)
{
s = Point(0, -c / b);
e = Point(1, -c / b);
}
else if (sgn(b) == 0)
{
s = Point(-c / a, 0);
e = Point(-c / a, 1);
}
else
{
s = Point(0, -c / b);
e = Point(1, (-c-a) / b);
}
}
//得到s-e方向单位向量
Point getV()
{
return e-s;
}
void input()
{
s.input();
e.input();
}
void adjust()
{
if (e < s) swap(s, e);
}
//返回线段的长度
double length()
{
return s.distance(e);
}
//返回直线倾斜角
double angle()
{
double k = atan2(e.y - s.y, e.x - s.x);
if (sgn(k) < 0) k += pi;
if (sgn(k - pi) == 0) k -= pi;
return k;
}
//点和直线关系
//1 在左侧
//2 在右侧
//3 在直线上
int relation(Point p)
{
int c = sgn( (p - s) ^ (e - s) );
if (c < 0) return 1;
else if (c > 0) return 2;
return 3;
}
//点在线段上的判断
bool pointonseg(Point p)
{
return sgn((p - s) ^ (e - s)) == 0 && sgn((p - s) * (p - e)) <= 0;
}
//判断量直线平行或重合
bool parallel(Line v)
{
return sgn((e - s) ^ (v.e - v.s)) == 0;
}
//两线段相交判断
//2 规范相交
//1 非规范相交-过端点
//0 不相交
int segcrossseg(Line v)
{
int d1 = sgn((e-s)^(v.s-s));
int d2 = sgn((e-s)^(v.e-s));
int d3 = sgn((v.e-v.s)^(s-v.s));
int d4 = sgn((v.e-v.s)^(e-v.s));
if((d1^d2)==-2&&(d3^d4)==-2) return 2;
return ((d1==0&&sgn((v.s-s)*(v.s-e))<=0)||(d2==0&&sgn((v.e-s)*(v.e-e))<=0)||(d3==0&&sgn((s-v.s)*(s-v.e))<=0)||(d4==0&&sgn((e-v.s)*(e-v.e))<=0));
}
Point lineprog(Point p)
{
return s + ( ((e - s) * ((e - s) * (p - s))) / ((e - s).len2()) );
}
Point symmetrypoint(Point p)
{
Point q = lineprog(p);
return Point(2.0 * q.x - p.x, 2.0 * q.y - p.y);
}
double dispointtoline(Point p)
{
return fabs((p - s) ^ (e - s)) / length();
}
double dispointtoseg(Point p)
{
if (sgn((p-s)*(e-s))<0 || sgn((p-e)*(s-e))<0)
return min(p.distance(s), p.distance(e));
return dispointtoline(p);
}
//两直线关系
//0 平行
//1 重合
//2 相交
int linecrossline(Line v)
{
if((*this).parallel(v)) return v.relation(s)==3;
return 2;
}
Point crosspoint(Line v)
{
double a1=(v.e-v.s)^(s-v.s);
double a2=(v.e-v.s)^(e-v.s);
return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
}
};
const int maxn = 1005;
double dp[maxn];
Line seg[maxn];
Point p[maxn];
int pcnt,lcnt;
int main()
{
double x,ya,yb,yc,yd;
int n;
while(scanf("%d",&n)!=EOF)
{
if(n==-1) break;
pcnt=0,lcnt=0;
p[++pcnt]=Point(0,5);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf%lf",&x,&ya,&yb,&yc,&yd);
p[++pcnt]=Point(x,ya);
p[++pcnt]=Point(x,yb);
p[++pcnt]=Point(x,yc);
p[++pcnt]=Point(x,yd);
seg[++lcnt]=Line(Point(x,0),Point(x,ya));
seg[++lcnt]=Line(Point(x,yb),Point(x,yc));
seg[++lcnt]=Line(Point(x,yd),Point(x,10));
}
p[++pcnt]=Point(10,5);
dp[1]=0.0;
for(int i=2;i<=pcnt;i++) dp[i]=1e20;
for(int i=2;i<=pcnt;i++)
{
for(int j=1;j<i;j++)
{
Line tmp(p[i],p[j]);
int flag=0;
for(int k=1;k<=(i-2)/4*3;k++)//对所有在这个点左边的线段判交,有交点则不能松弛
{
if(seg[k].segcrossseg(tmp)==2)
{
flag=1;
break;
}
}
if(flag==0) dp[i]=min(dp[i],dp[j]+tmp.length());
}
}
printf("%.2f\n",dp[pcnt]);
}
}