99国产欧美久久久精品,欧美精品97,国产精品欧美精品

pku 3072

2009年7月26日

題目鏈接：PKU 3072 Robot

分類：角度旋轉+Dijkastra

題目分析與算法原型
此題也算是最短路的一個變形，計算代價的時候加入了每3個點，兩條邊的夾角的度數，因此需要自己好好的推算一下角度的公式，題目已經提示了用atan2(double,double)這個函數，所以計算的時候把握好3個點中以哪個點為旋轉點，關于旋轉可以有兩個方向，取小于180度的那個方向

Code:

1

#include<stdio.h>
2

#include<string.h>
3

#include<math.h>
4

#define max 1000000000
5

#define len 25
6

#define pi acos(-1.0)
7

int r,n,visit[len],path[len];
9

double x[len],y[len],map[len][len],dis[len];
10

bool find;
11

void init()
13

{
14

int i,j;
15

for(i=1;i<=n;i++)
16

for(j=1;j<=n;j++)
17

{
18

if(i==j)map[i][j]=0;
19

else
20

{
21

double l=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
22

if(l>r)map[i][j]=max;
23

else map[i][j]=l;
24

}
25

}
26

}
27

double degree(int start,int mid,int end,bool change)
28

{
29

double ds,d1,d2;
30

if(!change)d1=atan2(y[mid]-y[start],x[mid]-x[start])*180/pi;
32

else d1=atan2(y[start]-y[mid],x[start]-x[mid])*180/pi;
33

d2=atan2(y[end]-y[mid],x[end]-x[mid])*180/pi;
34

if(d1<0)d1+=360;
35

if(d2<0)d2+=360;
36

ds=fabs(d2-d1);
37

if(ds>180)ds=360-ds;
38

return ds;
39

}
40

void dij(int v0,int v)
41

{
42

int i,j,u;
43

for(i=1;i<n;i++)
44

{
45

if(i!=v0&&map[v0][i]<max)
46

{
47

double t=degree(n,v0,i,true);
48

dis[i]=map[v0][i]+t;
49

}
50

else dis[i]=map[v0][i];
51

if(i!=v0&&dis[i]<max)path[i]=v0;
53

else path[i]=-1;
54

}
55

dis[n]=map[v0][n];
56

visit[v0]=1;
57

for(i=1;i<n;i++)
58

{
59

double min=max;
60

for(j=1;j<=n;j++)
61

if(!visit[j]&&dis[j]<min)
62

{
63

u=j;
64

min=dis[j];
65

}
66

if(min==max)return ;
67

if(u==v)
69

{
70

find=true;
71

return ;
72

}
73

visit[u]=1;
74

for(j=1;j<=n;j++)
75

if(!visit[j]&&map[u][j]<max)
76

{
77

double tt=degree(path[u],u,j,false);
78

if(dis[u]+map[u][j]+tt<dis[j])
79

{
80

dis[j]=dis[u]+map[u][j]+tt;
81

path[j]=u;
82

}
83

}
84

}
85

return ;
86

}
87

int main()
89

{
90

int i;
91

while(scanf("%d%d",&r,&n)!=EOF)
92

{
93

if(r==-1&&n==-1)break;
94

for(i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
95

find=false;
96

init();
97

memset(visit,0,sizeof(visit));
98

dij(1,n);
99

if(find)printf("%d\n",(int)(dis[n]+0.5));
100

else printf("impossible\n");
101

}
102

return 0;
103

}
104

posted on 2009-07-26 17:49 蝸牛也Coding 閱讀(278) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

pku 3072

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜