##Meaning:
Now I'll give you a plan of the bedroom. There are 0 to 18 walls (perpendicular to the x axis) in the bedroom
Fixed start point (0, 5), end point (10, 5)
Without going through the wall, you are required to find the shortest route from the beginning to the end
##Thinking:
First of all, the topic is well understood, that is, to find the shortest route from the starting point to the ending point without hitting the wall
First of all, we can know that the straight line between two points is the shortest,
So the best route is either a straight line (there is no wall between the starting point and the ending point)
Or it is formed by splicing segments passing through the endpoints of some walls (why the endpoints? The added segments do not pass through the endpoints, for example, from the empty space between two walls
If white passes through, the segment can always slope up or down to the end of the wall, so the length is smaller)
It can be thought that the starting point of the line segment has been fixed (the starting point is not necessarily (0,5)), and the end point of the line segment is at a point on the line where the wall perpendicular to the x axis is located. Due to the symmetry, it can be seen that
The minimum value of the line segment is that the end point of the line segment is parallel to the starting point and parallel to the x-axis. If it cannot be parallel (blocked by the wall), the closer it is to this parallel axis, the shorter the length of the line segment,
This shortest extreme case can only be obtained at the end of the wall.
At the beginning, my idea is dp, layered by walls. It can be seen that there are n layers from the starting point to the end point, and each layer has 3 walls. Then the shortest route through an end point of the current layer
1 or the length of the line segment from this end point of the wall on the current floor to the starting point (if any)
2 or it is the line segment from this end point to an end point on the previous wall, plus the distance from the starting point to this line segment (that is, the length of multiple line segments is added)
//In fact, I personally feel that the time complexity of this algorithm is almost the same as that of violent solution (because the data is very small and can be violent). The second point to note is:
//Direct arrival is very important, because if the minimum values of the endpoints of each layer are simply enumerated and added, the result will be greater than the optimal solution, because if the endpoints of the current layer and a wall of the previous 2 layers, 3 layers or even many layers can be directly connected, the minimum distance between these two points is obviously the length of the direct connection
#Specific code
##Main function implementation part
int n,wall_index;
double dp[200][200];/*dp Array means: dp[i][n]
Is the shortest distance from the starting point to the endpoint of the nth wall on the i-th floor
Each wall has only 4 endpoints
*/
Line walls[300][40];
/*
Line It is a class of lines. The computational geometry template behind the specific implementation will have
walls[i][n]It means the nth wall of the i-th wall
*/
Point points[300][40];
/*
Point Class point is
points[i][n]It means the nth endpoint of the i-th wall
*/
Point start_point;//starting point
Line temp_path;
bool is_cross(Line ttt,int nn,int index2)//Judge whether ttt this line has an intersection with a wall between the index2 nd wall and the nn wall
//If there is an intersection, it cannot be directly connected, and because the line segment is between the index2 layer and the nn layer wall, only the endpoint of this part of the wall is judged
{
for(int i=index2;i<nn;i++)
{
for(int u=0;u<3;u++)
if(ttt.linecrossseg(walls[i][u])>0) return false;
//The function linecrossseg of the Line class is to judge whether the Line intersects the Line segment wall[i][u]
}
return true;
}
void get_dis(int pre,int index)//pre is the number of layers where the current wall endpoint is located, and index is the serial number of the layer where the current wall endpoint is located
{
Line temp;
temp.e=points[pre][index];//temp.e is the end point of the line segment, temp S is the starting point of the line segment
temp.s=start_point;
if(is_cross(temp,pre,0))//If the current endpoint can be directly connected to the starting point, the shortest distance is the two-point distance
{
dp[pre][index]=dis(start_point.x,start_point.y,temp.e.x,temp.e.y);return ;
// Find the distance between two points and return
//dis function is a function to calculate the distance between two points. There will be a following geometric template
}
for(int u=0;u<pre;u++)//If it cannot be directly connected to the starting point, traverse the previous point to find the shortest distance from the starting point to the point
for(int i=0;i<4;i++)
{
temp.s=points[u][i];//Note that s
if(is_cross(temp,pre,u+1)) //Judge whether the traversed endpoint points[u][i] and the current endpoint points[pre][index] can be directly connected
//If you can, compare whether the distance at this time is smaller than dp[pre][index]. If it is smaller, refresh dp[pre][index]
dp[pre][index]=min(dp[pre][index],dp[u][i]+
dis(points[u][i].x,points[u][i].y,
points[pre][index].x,points[pre][index].y));
}
}
void get_ans()//Traverse the end of the wall from 0dao-1 and refresh the minimum distance
{
for(int i=0;i<n;i++)
{
for(int u=0;u<4;u++)
get_dis(i,u);
}
get_dis(n,0);//Finally, take the starting point as the endpoint of the nth layer wall and traverse it for the last time
}
int main()
{
double x,y1,y2,y3,y4;
start_point.x=0;
start_point.y=5;
while(scanf("%d",&n))
{
if(n==-1) break;
wall_index=n;
for(int i=0;i<30;i++)
for(int u=0;u<20;u++)
dp[i][u]=100000;
//printf("%f))\n",dp[n][0]);
for(int i=0;i<n;i++)
{
scanf("%lf%lf%lf%lf%lf",&x,&y1,&y2,&y3,&y4);
walls[i][2].s.x=walls[i][2].e.x=
walls[i][1].s.x= walls[i][1].e.x=
walls[i][0].s.x= walls[i][0].e.x=x;
walls[i][0].s.y=0;
walls[i][0].e.y=y1;//This part is the data reading of walls array and points array
walls[i][1].s.y=y2;
walls[i][1].e.y=y3;
walls[i][2].s.y=y4;
walls[i][2].e.y=10;
points[i][0]=walls[i][0].e;
points[i][1]=walls[i][1].s;
points[i][2]=walls[i][1].e;
points[i][3]=walls[i][2].s;
}
points[n][0].x=10;//Set the end point to the 0th end point of the nth wall
points[n][0].y=5;
get_ans();
printf("%.2f\n",dp[n][0]);
//According to the meaning of dp array, the optimal solution exists dp[n][0], that is, the shortest distance from the starting point to the end point
}
}
##Computational geometry template used
// `Calculation geometry template`
const double eps = 1e-8;
const double pi = acos(-1.0);
const int maxp = 1010;
//`Compares a double to zero`
int sgn(double x){
if(fabs(x) < eps)return 0;
if(x < 0)return -1;
else return 1;
}
double dis(double x1,double y1,double x2,double y2){
return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
//When establishing a straight line, it is necessary to judge whether two points form a line segment
//square of a double
inline double sqr(double x){return x*x;}
/*
* Point
* Point() - Empty constructor
* Point(double _x,double _y) - constructor
* input() - double input
* output() - %.2f output
* operator == - compares x and y
* operator < - compares first by x, then by y
* operator - - return new Point after subtracting curresponging x and y
* operator ^ - cross product of 2d points
* operator * - dot product
* len() - gives length from origin
* len2() - gives square of length from origin
* distance(Point p) - gives distance from p
* operator + Point b - returns new Point after adding curresponging x and y
* operator * double k - returns new Point after multiplieing x and y by k
* operator / double k - returns new Point after divideing x and y by k
* rad(Point a,Point b)- returns the angle of Point a and Point b from this Point
* trunc(double r) - return Point that if truncated the distance from center to r
* rotleft() - returns 90 degree ccw rotated point
* rotright() - returns 90 degree cw rotated point
* rotate(Point p,double angle) - returns Point after rotateing the Point centering at p by angle radian ccw
*/
struct Point{
double x,y;
Point(){}
Point(double _x,double _y){
x = _x;
y = _y;
}
void input(){
scanf("%lf%lf",&x,&y);
}
void output(){
printf("%.2f %.2f\n",x,y);
}
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);
}
//Cross product
double operator ^(const Point &b)const{
return x*b.y - y*b.x;
}
//Dot product
double operator *(const Point &b)const{
return x*b.x + y*b.y;
}
//Return length
double len(){
return hypot(x,y);//Library function
}
//Returns the square of the length
double len2(){
return x*x + y*y;
}
//Returns the distance between two points
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);
}
//`Calculate the angle between pa and pb`
//`Is to find the angle between a and B at this point`
//`Test LightOJ1203`
double rad(Point a,Point b){
Point p = *this;
return fabs(atan2( fabs((a-p)^(b-p)),(a-p)*(b-p) ));
}
//`Into a vector of length r`
Point trunc(double r){
double l = len();
if(!sgn(l))return *this;
r /= l;
return Point(x*r,y*r);
}
//`Rotate 90 degrees counterclockwise`
Point rotleft(){
return Point(-y,x);
}
//`Rotate 90 degrees clockwise`
Point rotright(){
return Point(y,-x);
}
//`Rotate the angle counterclockwise around point p`
Point rotate(Point p,double angle){
Point v = (*this) - p;
double c = cos(angle), s = sin(angle);
return Point(p.x + v.x*c - v.y*s,p.y + v.x*s + v.y*c);
}
};
/*
* Stores two points
* Line() - Empty constructor
* Line(Point _s,Point _e) - Line through _s and _e
* operator == - checks if two points are same
* Line(Point p,double angle) - one end p , another end at angle degree
* Line(double a,double b,double c) - Line of equation ax + by + c = 0
* input() - inputs s and e
* adjust() - orders in such a way that s < e
* length() - distance of se
* angle() - return 0 <= angle < pi
* relation(Point p) - 3 if point is on line
* 1 if point on the left of line
* 2 if point on the right of line
* pointonseg(double p) - return true if point on segment
* parallel(Line v) - return true if they are parallel
* segcrossseg(Line v) - returns 0 if does not intersect
* returns 1 if non-standard intersection
* returns 2 if intersects
* linecrossseg(Line v) - line and seg
* linecrossline(Line v) - 0 if parallel
* 1 if coincides
* 2 if intersects
* crosspoint(Line v) - returns intersection point
* dispointtoline(Point p) - distance from point p to the line
* dispointtoseg(Point p) - distance from p to the segment
* dissegtoseg(Line v) - distance of two segment
* lineprog(Point p) - returns projected point p on se line
* symmetrypoint(Point p) - returns reflection point of p over se
*
*/
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);
}
//`Determine the straight line according to a point and inclination 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=0
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);
}
}
void input(){
s.input();
e.input();
}
void adjust(){
if(e < s)swap(s,e);
}
//Find the length of line segment
double length(){
return s.distance(e);
}
//`Return straight line inclination angle 0 < = angle < pi`
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;
}
//`Relationship between point and line`
//`1 on the left`
//`2 on the right`
//`3 on a straight line`
int relation(Point p){
int c = sgn((p-s)^(e-s));
if(c < 0)return 1;
else if(c > 0)return 2;
else return 3;//c==0
}
// Judgment of point on line segment
bool pointonseg(Point p){
return sgn((p-s)^(e-s)) == 0 && sgn((p-s)*(p-e)) <= 0;
}
//`Two vectors are parallel (corresponding lines are parallel or coincident)`
bool parallel(Line v){
return sgn((e-s)^(v.e-v.s)) == 0;
}
//`Intersection judgment of two line segments`
//`2 specification intersection`
//`1 nonstandard intersection`
//`0 disjoint`
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);
}
//`Intersection judgment of line and line segment`
//`-*this line -v seg`
//`2 specification intersection`
//`1 nonstandard intersection`
//`0 disjoint`
int linecrossseg(Line v){
int d1 = sgn((e-s)^(v.s-s));
int d2 = sgn((e-s)^(v.e-s));
if((d1^d2)==-2) return 2;
return (d1==0||d2==0);
}
//`Two linear relationship`
//`0 parallel`
//`1 coincidence`
//`2 intersection`
int linecrossline(Line v){
if((*this).parallel(v))
return v.relation(s)==3;
return 2;
}
//`Find the intersection of two lines`
//`Ensure that the two straight lines are not parallel or coincide`
//Similar triangle proof!
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));
}
//Distance from point to line
double dispointtoline(Point p){
return fabs((p-s)^(e-s))/length();
}
//Distance from point to segment
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);
}
//`Returns the distance from segment to segment`
//`The premise is that the two line segments do not intersect, and the intersection distance is 0`
double dissegtoseg(Line v){
return min(min(dispointtoseg(v.s),dispointtoseg(v.e)),min(v.dispointtoseg(s),v.dispointtoseg(e)));
}
//`Returns the projection of point p on a straight line`
Point lineprog(Point p){
return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()) );
}
//`Returns the point of symmetry of point p with respect to a straight line`
Point symmetrypoint(Point p){
Point q = lineprog(p);
return Point(2*q.x-p.x,2*q.y-p.y);
}
};