首页 > 代码库 > hdu 4885 (n^2*log(n)判断三点共线建图)+最短路
hdu 4885 (n^2*log(n)判断三点共线建图)+最短路
题意:车从起点出发,每次只能行驶L长度,必需加油到满,每次只能去加油站或目的地方向,路过加油站就必需进去加油,问最小要路过几次加油站。
开始时候直接建图,在范围内就有边1.跑最短了,再读题后发现,若几个点共线,且都在范围内,那么中间有点的俩头的点就不能有边,否则与条件相悖。关键是怎么用n^2*logn,的复杂度判断三点共线:点先按X排序,考察每个点i时候,第二个点j,若直线ij斜率已经存在,则不能添加了,查找是否存在,用容器就行(map\set)都是logn的,所以满足要求。之后最短路即可。
#include<iostream> #include<cstring> #include<queue> #include<cstdio> #include<algorithm> #include<map> using namespace std; const int inf=0x3f3f3f3f; struct points { long long x,y; }; long long inline getdis(points a,points b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } bool my(points a,points b) { if(a.x!=b.x)return a.x<b.x; else return a.y<b.y; } int n;long long l; points po[1005]; int dis[1005][1008]; int d[1005];int inq[1005]; int ans=0;points s,t;int nums,numt; double inline getk(points a,points b) //获得斜率 { if(b.x==a.x)return inf; return (a.y-b.y)*1.0/(a.x-b.x); } void spfa() { for(int i=0;i<n+2;i++) { d[i]=inf; inq[i]=0; } queue<int>q; inq[nums]=1; d[nums]=0; q.push(nums); while(!q.empty()) { int cur=q.front(); q.pop(); inq[cur]=0; for(int i=0;i<n+2;i++) { if(d[i]>dis[cur][i]+d[cur]) { d[i]=dis[cur][i]+d[cur]; if(!inq[i]) { q.push(i); inq[i]=1; } } } } return ; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&l); scanf("%d%d",&po[0].x,&po[0].y); scanf("%d%d",&po[n+1].x,&po[n+1].y); s.x=po[0].x; s.y=po[0].y; t.x=po[n+1].x; t.y=po[n+1].y; for(int i=1;i<=n;i++) scanf("%d%d",&po[i].x,&po[i].y); sort(po,po+n+2,my); for(int i=0;i<=n+1;i++) //起点,终点 { if(po[i].x==s.x&&po[i].y==s.y)nums=i; if(po[i].x==t.x&&po[i].y==t.y)numt=i; } for(int i=0;i<=n+1;i++) { map<double,int>ma; for(int j=i+1;j<=n+1;j++) { if(getdis(po[i],po[j])<=l*l) //在距离范围内的再查找。 { double tempk=getk(po[i],po[j]); if(ma.find(tempk)!=ma.end()) { dis[j][i]=dis[i][j]=inf; } else { dis[j][i]=dis[i][j]=1; ma[tempk]=1; } } else dis[j][i]=dis[i][j]=inf; } } spfa(); if(d[numt]==inf) printf("impossible\n"); else printf("%d\n",d[numt]-1); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。