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

隨筆 - 87  文章 - 279  trackbacks - 0
<2006年10月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

潛心看書研究!

常用鏈接

留言簿(19)

隨筆分類(81)

文章分類(89)

相冊

ACM OJ

My friends

搜索

  •  

積分與排名

  • 積分 - 219411
  • 排名 - 118

最新評論

閱讀排行榜

評論排行榜

BellmanFord實現

The Doors

Time limit: 1 Seconds?? Memory limit: 32768K??
Total Submit: 214?? Accepted Submit: 63??

You are to find the length of the shortest path through a chamber containing obstructing walls. The chamber will always have sides at x = 0, x = 10, y = 0, and y = 10. The initial and final points of the path are always (0, 5) and (10, 5). There will also be from 0 to 18 vertical walls inside the chamber, each with two doorways. The figure below illustrates such a chamber and also shows the path of minimal length.


Input

The input data for the illustrated chamber would appear as follows.

2
4 2 7 8 9
7 3 4.5 6 7

The first line contains the number of interior walls. Then there is a line for each such wall, containing five real numbers. The first number is the x coordinate of the wall (0 < x < 10), and the remaining four are the y coordinates of the ends of the doorways in that wall. The x coordinates of the walls are in increasing order, and within each line the y coordinates are in increasing order. The input file will contain at least one such set of data. The end of the data comes when the number of walls is -1.


Output

The output file should contain one line of output for each chamber. The line should contain the minimal path length rounded to two decimal places past the decimal point, and always showing the two decimal places past the decimal point. The line should contain no blanks.


Sample Input

1
5 4 6 7 8
2
4 2 7 8 9
7 3 4.5 6 7
-1


Sample Output

10.00
10.06

#include?<iostream>
#include?
<cmath>
using?namespace?std;

const?double?INF?=?2000000000;
const?int?MAXN?=?100;

struct?POINT
{
????
double?x,?y;
}
;
struct?EDGE
{
????
int?u,?v;
}
;

double?g[MAXN][MAXN];
EDGE?e[MAXN
*MAXN];
int?n;
int?i,?j;
double?wX[20];
double?pY[20][4];
double?x;
POINT?p[MAXN];
int?pSize;
int?eSize;

double?Dis(POINT?a,?POINT?b)
{
????
return?sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}


double?Cross(double?x1,?double?y1,?double?x2,?double?y2,?double?x3,?double?y3)
{
????
return?(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
}


bool?IsOk(POINT?a,?POINT?b)
{
????
if?(a.x?>=?b.x)?return?false;
????
int?i,?j;
????
bool?flag?=?true;
????i?
=?0;
????
while?(wX[i]?<=?a.x?&&?i?<?n)?{
????????i
++;
????}

????
while?(wX[i]?<?b.x?&&?i?<?n)?{
????????
if?(Cross(a.x,?a.y,?b.x,?b.y,?wX[i],?0)
????????
*Cross(a.x,?a.y,?b.x,?b.y,?wX[i],?pY[i][0])?<?0
????????
||?Cross(a.x,?a.y,?b.x,?b.y,?wX[i],?pY[i][1])
????????
*Cross(a.x,?a.y,?b.x,?b.y,?wX[i],?pY[i][2])?<?0
????????
||?Cross(a.x,?a.y,?b.x,?b.y,?wX[i],?pY[i][3])
????????
*Cross(a.x,?a.y,?b.x,?b.y,?wX[i],?10)?<?0)?{
????????????flag?
=?false;
????????????
goto?ou;
????????}

????????i
++;
????}

????ou:;
????
return?flag;
}


double?BellmanFord(int?beg,?int?end)
{
????
double?d[MAXN];
????
int?i,?j;
????
for?(i=0;?i<MAXN;?i++)?{
????????d[i]?
=?INF;
????}

????d[beg]?
=?0;
????
bool?ex?=?true;
????
for?(i=0;?i<pSize?&&?ex;?i++)?{
????????ex?
=?false;
????????
for?(j=0;?j<eSize;?j++)?{
????????????
if?(d[e[j].u]?<?INF?&&?d[e[j].v]?>?d[e[j].u]?+?g[e[j].u][e[j].v])?{
????????????????d[e[j].v]?
=?d[e[j].u]?+?g[e[j].u][e[j].v];
????????????????ex?
=?true;
????????????}

????????}

????}

????
return?d[end];
}


void?Solve()
{
????p[
0].x?=?0;
????p[
0].y?=?5;
????pSize?
=?1;
????
for?(i=0;?i<n;?i++)?{
????????scanf(
"%lf",?&wX[i]);
????????
for?(j=0;?j<4;?j++)?{
????????????p[pSize].x?
=?wX[i];
????????????scanf(
"%lf",?&p[pSize].y);
????????????pY[i][j]?
=?p[pSize].y;
????????????pSize
++;
????????}

????}

????p[pSize].x?
=?10;
????p[pSize].y?
=?5;
????pSize
++;
????
for?(i=0;?i<pSize;?i++)?{
????????
for?(j=0;?j<pSize;?j++)?{
????????????g[i][j]?
=?INF;
????????}

????}

????eSize?
=?0;
????
for?(i=0;?i<pSize;?i++)?{
????????
for?(j=i+1;?j<pSize;?j++)?{
????????????
if?(IsOk(p[i],?p[j]))?{
????????????????g[i][j]?
=?Dis(p[i],?p[j]);
????????????????e[eSize].u?
=?i;
????????????????e[eSize].v?
=?j;
????????????????eSize
++;
????????????}

????????}

????}

????printf(
"%.2lf\n",?BellmanFord(0,?pSize-1));
}


int?main()
{
????
while?(scanf("%d",?&n)?!=?EOF)
????
{
????????
if?(n?==?-1)?break;
????????Solve();
????}

????
return?0;
}

posted on 2006-10-09 01:05 閱讀(500) 評論(0)  編輯 收藏 引用 所屬分類: ACM題目
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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资源网站| 亚洲影院免费观看| 国产日产欧产精品推荐色 | 国产亚洲午夜| 久久久精品国产99久久精品芒果| 久久精品国亚洲| 亚洲国产一区二区三区a毛片| 亚洲国产美女| 欧美日韩影院| 欧美专区在线播放| 久久一区免费| 一区二区三区不卡视频在线观看| 在线亚洲免费视频| 精品电影一区| 99精品视频免费| 黑人一区二区| 亚洲久色影视| 国产一区二区三区在线观看精品 | 久久精品国产欧美激情| 影音先锋亚洲视频| 亚洲精品亚洲人成人网| 国产精品自拍网站| 欧美日韩一区二区三区免费看| 欧美一区二区高清| 欧美mv日韩mv国产网站app| 亚洲综合色婷婷| 老司机久久99久久精品播放免费| 亚洲自拍偷拍麻豆| 美女成人午夜| 久久九九有精品国产23| 欧美日韩国产成人在线91| 久久久夜精品| 国产精品影音先锋| 亚洲精品日韩精品| 伊人久久大香线蕉av超碰演员| 夜夜精品视频一区二区| 亚洲国产成人高清精品| 午夜精品久久久久久久男人的天堂| 亚洲精品久久久久| 久久久久久欧美| 欧美专区中文字幕| 国产精品vvv| 亚洲精品美女在线| 亚洲国产成人久久综合| 欧美一级专区免费大片| 亚洲女ⅴideoshd黑人| 欧美激情视频网站| 欧美顶级大胆免费视频| 国产一区二区精品| 午夜欧美视频| 久久激情一区| 国产欧美在线视频| 亚洲欧美国产制服动漫| 亚洲欧美视频一区| 欧美精品一区在线发布| 欧美激情一区二区三区高清视频 | 欧美激情免费观看| 亚洲国产片色| 亚洲一级在线| 亚洲尤物视频在线| 国产精品国产三级国产普通话蜜臀 | 国产丝袜一区二区| 亚洲一区二区三区激情| 亚洲专区免费| 国产精品乱码一区二三区小蝌蚪| 日韩视频免费观看高清完整版| 99热这里只有成人精品国产| 欧美另类高清视频在线| 亚洲日本视频| 亚洲欧美欧美一区二区三区| 欧美日韩在线播放| 亚洲图片在线观看| 久久精品国产亚洲aⅴ| 狠狠色丁香久久婷婷综合丁香| 久久国产精品黑丝| 欧美国产日韩视频| 一区二区三区四区五区视频| 国产精品久久久久久久久久ktv| 亚洲天堂av图片| 久久国产精品亚洲va麻豆| 韩国免费一区| 欧美激情免费在线| 亚洲午夜久久久久久尤物| 欧美在线www| 亚洲国产高清一区| 欧美日韩在线一区二区三区| 亚洲一品av免费观看| 久久婷婷一区| 一区二区精品国产| 国产一区二区你懂的| 欧美凹凸一区二区三区视频| 国产精品99久久久久久久vr| 久久网站热最新地址| 一本久道久久综合狠狠爱| 国产精品一区免费视频| 老牛嫩草一区二区三区日本| 一本色道久久综合一区| 久久男人资源视频| 一区二区av在线| 精品成人乱色一区二区| 欧美日韩一二三区| 久久久久五月天| 亚洲天堂偷拍| 亚洲激情第一页| 久久精品一区四区| 夜夜嗨av一区二区三区网页 | 欧美α欧美αv大片| 亚洲欧美视频| 99天天综合性| 欧美韩国一区| 久久久999成人| 午夜久久久久久久久久一区二区| 亚洲激情二区| 黄色成人免费网站| 国产精品视频第一区| 欧美精品亚洲精品| 老牛影视一区二区三区| 欧美影院精品一区| 亚洲欧美国产毛片在线| avtt综合网| 亚洲卡通欧美制服中文| 欧美成人伊人久久综合网| 久久精品国产精品| 亚洲欧美一级二级三级| 一区二区激情小说| 99精品国产福利在线观看免费| 亚洲第一成人在线| 激情国产一区| 国内欧美视频一区二区| 国产精品一二三| 国产精品久久久久久久久婷婷| 欧美日韩精品二区| 欧美激情综合五月色丁香| 免费不卡亚洲欧美| 美女黄网久久| 免费成人毛片| 欧美福利视频| 欧美久久一级| 国产精品成人免费精品自在线观看| 欧美日韩精品伦理作品在线免费观看 | 欧美激情四色| 亚洲高清资源综合久久精品| 麻豆精品精品国产自在97香蕉| 久久全国免费视频| 麻豆精品视频| 亚洲国产精品一区制服丝袜 | 日韩一级片网址| 亚洲天堂男人| 欧美一区二区三区在线| 久久精品国产2020观看福利| 久久亚洲二区| 欧美黄色小视频| 国产精品极品美女粉嫩高清在线| 国产精品久久久久久久app| 国产日韩精品在线观看| 黑人巨大精品欧美一区二区| 亚洲经典自拍| 亚洲天堂成人| 久久精品五月| 欧美激情精品久久久久久蜜臀| 亚洲人线精品午夜| 亚洲愉拍自拍另类高清精品| 欧美主播一区二区三区美女 久久精品人| 欧美一区二区三区视频免费| 鲁大师影院一区二区三区| 欧美精品激情在线| 国产乱码精品一区二区三区五月婷 | 久久综合伊人| 亚洲精品乱码久久久久久| 9l视频自拍蝌蚪9l视频成人| 午夜在线精品| 欧美激情按摩| 国产欧美日韩视频在线观看| 亚洲国产精品t66y| 亚洲免费网址| 欧美福利网址| 亚洲专区一区二区三区| 麻豆国产精品va在线观看不卡| 欧美日韩国产影片| 精品999日本| 亚洲男女毛片无遮挡| 欧美福利视频网站| 亚洲欧美在线网| 欧美人成在线视频| 影音先锋日韩精品| 性色av香蕉一区二区| 亚洲高清视频在线观看| 亚洲欧美一区二区精品久久久| 欧美激情91| 亚洲盗摄视频| 久久九九热re6这里有精品| 亚洲精品日产精品乱码不卡| 久久激情久久| 国产伦精品一区二区三区免费迷| 亚洲精品少妇网址| 久久全国免费视频| 午夜精品久久久久久久99水蜜桃| 欧美另类亚洲|