The Doors POJ - 1556
程序员文章站
2022-04-02 17:42:13
...
对于横坐标不同的两个点 判断是否可以通过直线相连 即两者间连线不与其他线段相交
若符合条件则加一条边 最后通过dijkstra或spfa求解
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 0x3f3f3f3f3f3f3f3f
#define eps 1e-8
struct node1
{
double x;
double y1;
double y2;
};
struct node2
{
double x;
double y;
};
struct node3
{
int v;
double w;
int next;
};
struct node4
{
bool friend operator < (node4 n1,node4 n2)
{
return n1.w>n2.w;
}
int u;
double w;
};
node1 seg[100];
node2 point[100];
node3 edge[10000];
priority_queue <node4> que;
double dis[100];
int first[100],book[100];
int n,m,num;
double cal(node2 a,node2 b,node2 c)//AB X AC
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool judgeII(node2 a,node2 b,node2 c,node2 d)
{
if(cal(a,b,c)*cal(a,b,d)<eps&&cal(c,d,a)*cal(c,d,b)<eps)
{
return true;
}
else return false;
}
bool judgeI(int u,int v)
{
node2 tu,tv;
int i;
for(i=1;i<=m;i++)
{
if(fabs(seg[i].x-point[u].x)<eps||fabs(seg[i].x-point[v].x)<eps) continue;
tu.x=seg[i].x,tu.y=seg[i].y1;
tv.x=seg[i].x,tv.y=seg[i].y2;
if(judgeII(point[u],point[v],tu,tv)) return false;
}
return true;
}
double getdis(int u,int v)
{
return sqrt((point[v].x-point[u].x)*(point[v].x-point[u].x)+(point[v].y-point[u].y)*(point[v].y-point[u].y));
}
void addedge(int u,int v,double w)
{
edge[num].v=v;
edge[num].w=w;
edge[num].next=first[u];
first[u]=num++;
return;
}
double dijkstra()
{
node4 cur,tem;
double w;
int i,u,v;
while(!que.empty()) que.pop();
for(i=1;i<=n;i++)
{
dis[i]=N;
}
memset(book,0,sizeof(book));
tem.u=n-1,tem.w=0;
que.push(tem);
dis[n-1]=0;
while(!que.empty())
{
cur=que.top();
que.pop();
u=cur.u;
if(book[u]) continue;
book[u]=1;
for(i=first[u];i!=-1;i=edge[i].next)
{
v=edge[i].v,w=edge[i].w;
if(!book[v]&&dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
tem.u=v;
tem.w=dis[v];
que.push(tem);
}
}
}
return dis[n];
}
int main()
{
double x,y1,y2,y3,y4;
int i,j;
while(scanf("%d",&n)!=EOF)
{
if(n==-1) break;
for(i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf%lf",&x,&y1,&y2,&y3,&y4);
seg[3*i-2].x=x,seg[3*i-1].x=x,seg[3*i].x=x;
seg[3*i-2].y1=0,seg[3*i-2].y2=y1;
seg[3*i-1].y1=y2,seg[3*i-1].y2=y3;
seg[3*i].y1=y4,seg[3*i].y2=10;
point[4*i-3].x=x,point[4*i-2].x=x,point[4*i-1].x=x,point[4*i].x=x;
point[4*i-3].y=y1,point[4*i-2].y=y2,point[4*i-1].y=y3,point[4*i].y=y4;
}
point[4*n+1].x=0,point[4*n+1].y=5;
point[4*n+2].x=10,point[4*n+2].y=5;
memset(first,-1,sizeof(first));
m=3*n,n=4*n+2,num=0;
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
if(fabs(point[i].x-point[j].x)<eps) continue;
if(judgeI(i,j))
{
addedge(i,j,getdis(i,j));
addedge(j,i,getdis(i,j));
}
}
}
printf("%.2f\n",dijkstra());
}
return 0;
}