青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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
  8int r,n,visit[len],path[len];
  9double x[len],y[len],map[len][len],dis[len];
 10bool find;
 11
 12void 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}

 27double degree(int start,int mid,int end,bool change)
 28{
 29    double ds,d1,d2;
 30
 31    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}

 40void 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
 52        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
 68        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
 88int 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 閱讀(283) 評論(0)  編輯 收藏 引用


只有注冊用戶登錄后才能發表評論。
網站導航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            性色av一区二区三区| 国产一区二区三区在线播放免费观看 | 亚洲欧美日韩国产综合| 亚洲另类黄色| 99re国产精品| 国模私拍一区二区三区| 99视频精品在线| av成人毛片| 一区二区三区四区国产| 亚洲欧美日韩国产一区二区| 久久xxxx| 亚洲人成网站精品片在线观看 | 欧美国产日韩xxxxx| 欧美精品成人| 国产精品亚洲片夜色在线| 国产精品日韩在线观看| 在线精品视频免费观看| 亚洲桃色在线一区| 久久免费视频在线观看| 亚洲国产裸拍裸体视频在线观看乱了| 亚洲精品在线一区二区| 亚洲女人天堂av| 欧美成人激情视频| 国产精品尤物| 99国产精品国产精品久久| 欧美在线观看视频一区二区| 亚洲国产小视频在线观看| 亚洲免费在线视频一区 二区| 久热这里只精品99re8久| 欧美日韩1234| 一区二区亚洲精品| 午夜精品美女自拍福到在线 | 亚洲视频一区二区| 久久久亚洲高清| 一本大道久久精品懂色aⅴ| 久久久久久婷| 国产精品一级久久久| 亚洲精选中文字幕| 美女任你摸久久| 亚洲欧美文学| 国产精品久久久久久久电影| 亚洲国产精品一区二区三区| 午夜日韩在线观看| 亚洲精品久久7777| 久久乐国产精品| 国产午夜精品一区二区三区欧美| 一本到12不卡视频在线dvd| 欧美大片免费观看| 欧美在线视频在线播放完整版免费观看 | 亚洲娇小video精品| 久久久噜久噜久久综合| 国产欧美日韩免费| 亚洲欧美999| 久久久www成人免费毛片麻豆| 中文日韩在线| 欧美区在线播放| 亚洲精品一级| 亚洲国产一区二区视频| 久久久一本精品99久久精品66| 国模 一区 二区 三区| 久久国产精彩视频| 欧美影院视频| 黄色成人在线网站| 欧美成在线观看| 蜜桃av综合| 99国产精品99久久久久久粉嫩| 亚洲精品免费在线播放| 欧美理论片在线观看| 中文精品99久久国产香蕉| 日韩视频在线你懂得| 欧美日韩福利视频| 亚洲女人天堂成人av在线| 亚洲自拍高清| 国产欧美精品在线| 久久夜色精品国产亚洲aⅴ | 久久久久久久久久久久久久一区| 欧美一区二区日韩| 一区精品久久| 亚洲国内精品| 国产精品手机视频| 久久夜色精品亚洲噜噜国产mv| 久久综合一区二区| 一区二区高清在线观看| 亚洲一区二区三区色| 好吊成人免视频| 亚洲人成7777| 国产色综合网| 女人天堂亚洲aⅴ在线观看| 欧美大片第1页| 午夜日韩在线观看| 欧美14一18处毛片| 午夜在线视频观看日韩17c| 久久精品视频在线看| 日韩午夜精品| 欧美在线播放一区| 亚洲看片网站| 欧美亚洲尤物久久| 亚洲人成亚洲人成在线观看图片| 夜夜爽夜夜爽精品视频| 开心色5月久久精品| 亚洲视频一区二区在线观看| 久久精品免费看| 亚洲欧美国产视频| 免费国产一区二区| 久久精品一区二区国产| 欧美黄色大片网站| 久久噜噜噜精品国产亚洲综合 | 欧美一激情一区二区三区| 亚洲日本aⅴ片在线观看香蕉| 亚洲在线免费观看| 日韩一级视频免费观看在线| 欧美一区二区三区免费视| 中日韩视频在线观看| 99国产精品| 久久中文字幕导航| 国产精品你懂的在线欣赏| 欧美激情aaaa| 国产一区二区三区网站| 一区二区三区鲁丝不卡| 亚洲欧洲在线看| 久久精品国产精品亚洲综合 | 国内伊人久久久久久网站视频| 亚洲精品一区二区在线观看| 亚洲高清av在线| 久久aⅴ乱码一区二区三区| 亚洲欧美在线磁力| 欧美日韩系列| 亚洲美女视频在线观看| 亚洲精品九九| 欧美韩日亚洲| 亚洲黄色尤物视频| 亚洲人成网站精品片在线观看| 久久亚洲欧美| 免费中文日韩| 亚洲黑丝在线| 欧美高清视频免费观看| 亚洲动漫精品| 一区二区毛片| 欧美日韩在线三级| 一区二区三区回区在观看免费视频| 亚洲乱码日产精品bd| 欧美精品国产精品日韩精品| 亚洲国产电影| 99国产精品99久久久久久粉嫩| 欧美日韩视频在线一区二区| 中文有码久久| 久久精品亚洲热| 激情成人综合网| 免费欧美网站| 亚洲人成在线观看| 亚洲一区在线播放| 国产美女精品免费电影| 久久精品最新地址| 欧美激情亚洲另类| 亚洲婷婷综合久久一本伊一区| 国产精品扒开腿做爽爽爽软件| 亚洲欧美国产毛片在线| 麻豆精品91| 亚洲素人一区二区| 黑人极品videos精品欧美裸| 米奇777在线欧美播放| 日韩一区二区高清| 欧美在线观看www| 亚洲国产美女| 国产精品美腿一区在线看| 久久成人在线| 日韩亚洲国产欧美| 久久激情久久| 亚洲精品社区| 国产欧美精品久久| 免费视频久久| 午夜欧美精品| 亚洲茄子视频| 久久夜色精品一区| 亚洲视频免费| 亚洲国产高清视频| 国产精品热久久久久夜色精品三区| 久久久噜噜噜久噜久久| 在线视频精品| 亚洲国产一区二区a毛片| 久久av资源网| 亚洲天堂成人在线观看| 久久久久久综合| 亚洲二区在线视频| 国产精品外国| 欧美精品一区二区三区在线播放| 亚洲欧美精品伊人久久| 亚洲国产欧美久久| 久久久久久综合| 性欧美超级视频| 中文在线一区| 亚洲日韩第九十九页| 黄网站免费久久| 国产乱肥老妇国产一区二 | 亚洲在线中文字幕| 欧美韩日一区| 免费看亚洲片| 久久深夜福利| 久久精品亚洲精品| 午夜在线视频观看日韩17c|