哦天哪这个萨比提又浪费了我好几个小时。
我们在check的时候只考虑严格相交就行了，想了很久才注意到这一点。
然后就建图跑最短路，over。
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <iomanip>
#include <iostream>
typedef double db;
using namespace std;
const db eps=1e-;
const db pi=acos(-);
int sign(db k){
if (k>eps) return ; else if (k<-eps) return -; return ;
}
int cmp(db k1,db k2){return sign(k1-k2);}
struct point{
db x,y;
point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};}
point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
point operator * (db k1) const{return (point){x*k1,y*k1};}
point operator / (db k1) const{return (point){x/k1,y/k1};}
db abs(){ return sqrt(x*x+y*y);}
db dis(point k1){ return(*this-k1).abs();}
};
db cross(point k1,point k2){ return k1.x*k2.y-k1.y*k2.x; }
db dot(point k1,point k2){ return k1.x*k2.x+k1.y*k2.y;}
int intersect(db l1,db r1,db l2,db r2){
if (l1>r1) swap(l1,r1); if (l2>r2) swap(l2,r2); return cmp(r1,l2)!=-&&cmp(r2,l1)!=-;
}
int checkSS(point k1,point k2,point k3,point k4){
return //intersect(k1.x,k2.x,k3.x,k4.x)&&intersect(k1.y,k2.y,k3.y,k4.y)&&
sign(cross(k3-k1,k4-k1))*sign(cross(k3-k2,k4-k2))<&&
sign(cross(k1-k3,k2-k3))*sign(cross(k1-k4,k2-k4))<;
}
struct line{
point p[];
};
int checkSS(line a,line b){
return checkSS(a.p[],a.p[],b.p[],b.p[]);
}
int n;
db dis[];
struct node { //堆节点
int u;db d;
bool operator <(const node& rhs) const {
return d>rhs.d;
}
};
struct Edge { int v,nxt;db w;};
Edge e[];
int head[],cnt=;
void addEdge(int u,int v,db w) {
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void Dijkstra() {
for (int i=;i<=;i++) dis[i]=;
dis[]=;
priority_queue<node> Q; //堆
Q.push((node){,});
while (!Q.empty()) {
node fr=Q.top(); Q.pop();
int u=fr.u;db d=fr.d;
if (cmp(d,dis[u])>) continue;
for (int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;db w=e[i].w;
if (cmp(dis[u]+w,dis[v])<) {
dis[v]=dis[u]+w;
Q.push((node){v,dis[v]});
}
}
}
}
db yl,y2,y3,y4,x;
vector<line> v;
vector<point> g;
bool check(line tmp){
for(int i=;i<v.size();i++){
if(checkSS(tmp,v[i])){
return false;
}//return false;
}
return true;
}
int main(){
ios::sync_with_stdio(false);
cout<<fixed<<setprecision();
while (cin>>n&&n!=-){
g.push_back(point{,});
for(int i=;i<=n;i++){
cin>>x>>yl>>y2>>y3>>y4;
g.push_back(point{x,yl});
g.push_back(point{x,y2});
g.push_back(point{x,y3});
g.push_back(point{x,y4});
v.push_back(line{point{x,},point{x,yl}});
v.push_back(line{point{x,y2},point{x,y3}});
v.push_back(line{point{x,y4},point{x,}});
}
g.push_back(point{,});
int m=g.size();
for(int i=;i<m;i++){
for(int j=i+;j<m;j++){
if(check(line{g[i],g[j]})){
//printf("%d %d\n",i,j);
addEdge(i,j,g[i].dis(g[j]));
addEdge(j,i,g[i].dis(g[j]));
}
}
}
Dijkstra();
cout<<dis[m-]<<endl;
g.clear();
v.clear();
cnt=;
memset(head,, sizeof(head));
}
}
/**
2
4 2 7 8 9
7 3 4.5 6 7
-1
*/