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

隨筆 - 87  文章 - 279  trackbacks - 0
<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

潛心看書研究!

常用鏈接

留言簿(19)

隨筆分類(81)

文章分類(89)

相冊

ACM OJ

My friends

搜索

  •  

積分與排名

  • 積分 - 219408
  • 排名 - 118

最新評論

閱讀排行榜

評論排行榜

BellmanFord實(shí)現(xiàn)

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>
            免费日韩精品中文字幕视频在线| 欧美伊人久久久久久久久影院| 免费观看在线综合色| 久久久噜噜噜久噜久久| 亚洲国产另类久久精品| 最近看过的日韩成人| 欧美日韩在线影院| 久久精品观看| 欧美黑人多人双交| 先锋影音久久久| 另类综合日韩欧美亚洲| 一区二区三区四区在线| 亚洲专区在线| 亚洲精品老司机| 亚洲一线二线三线久久久| 亚洲电影有码| 一区二区欧美国产| 亚洲电影毛片| 亚洲天堂免费观看| 亚洲激情第一页| 午夜精品久久久久久久| 亚洲精品久久久久| 校园激情久久| 亚洲精品视频免费观看| 一本在线高清不卡dvd| 激情懂色av一区av二区av| aa级大片欧美| 亚洲人成在线影院| 亚洲欧美日韩精品综合在线观看| 91久久精品日日躁夜夜躁国产| 亚洲在线中文字幕| 夜夜躁日日躁狠狠久久88av| 久久久久久久久久久久久女国产乱 | 久久精品国产96久久久香蕉| 99riav国产精品| 久久久一本精品99久久精品66| 亚洲无限乱码一二三四麻| 久久夜色精品国产亚洲aⅴ| 亚洲欧美日韩国产另类专区| 欧美激情一区二区三区高清视频| 久久久久久9999| 国产精品亚洲综合色区韩国| 亚洲人成人一区二区在线观看| 国产一区免费视频| 亚洲欧美精品在线| 午夜免费在线观看精品视频| 欧美日本免费一区二区三区| 欧美激情精品久久久久久蜜臀| 国产婷婷色一区二区三区四区| 一区二区三区色| 亚洲午夜一区二区| 欧美日本免费| 99re这里只有精品6| 日韩午夜免费视频| 欧美高清在线一区二区| 欧美成人久久| 亚洲高清中文字幕| 噜噜噜噜噜久久久久久91| 另类春色校园亚洲| 狠狠爱综合网| 久久免费黄色| 免费在线欧美视频| 亚洲国产精品毛片| 久久亚洲欧美| 欧美激情影音先锋| 亚洲欧洲综合另类| 欧美日韩国产专区| 宅男精品导航| 欧美在线免费观看视频| 国产综合久久久久影院| 久久久91精品国产| 久久久久99| 亚洲国产岛国毛片在线| 免费观看亚洲视频大全| 欧美电影免费观看高清完整版| 亚洲精品偷拍| 国产精品国产精品| 欧美一区三区三区高中清蜜桃 | 在线观看三级视频欧美| 老司机一区二区| 亚洲福利视频网站| 亚洲一区美女视频在线观看免费| 国产精品美女在线观看| 久久精品色图| 亚洲毛片在线观看| 久久国产精品久久久久久久久久| 激情成人在线视频| 欧美国产成人精品| 欧美一区二区三区免费看| 欧美大片在线看| 欧美一二三视频| 亚洲高清电影| 国产精品入口麻豆原神| 久久综合图片| 中文精品在线| 亚洲电影免费观看高清完整版在线 | 亚洲欧美中日韩| 在线日韩av永久免费观看| 欧美日本视频在线| 久久久久久久一区| 一区二区三区成人精品| 欧美激情按摩在线| 欧美制服第一页| 一区二区三区精品视频| 1000部精品久久久久久久久| 欧美午夜精品一区二区三区| 久久夜色精品国产| 欧美一区二区三区四区在线观看| 日韩午夜剧场| 亚洲福利视频专区| 久久综合网络一区二区| 午夜精品久久久久久久久久久| 日韩视频免费在线观看| 精品91免费| 国产专区综合网| 国产精品亚洲不卡a| 欧美日韩中文字幕在线视频| 另类欧美日韩国产在线| 久久久久久久97| 西西人体一区二区| 亚洲欧美久久久| 亚洲午夜小视频| 一本色道久久88精品综合| 亚洲人成77777在线观看网| 欧美高清在线一区| 欧美freesex8一10精品| 久久午夜色播影院免费高清| 欧美综合国产| 久久成人这里只有精品| 亚洲欧美中文在线视频| 亚洲欧美日韩人成在线播放| 亚洲视频图片小说| 亚洲综合日本| 亚洲欧美日韩另类精品一区二区三区| 一本色道久久综合亚洲二区三区 | 一区二区av| 一区二区三区四区国产精品| 一区二区三区成人| 亚洲小视频在线观看| 亚洲视频在线观看视频| 亚洲一区二区免费视频| 亚洲一区二区高清| 亚洲欧美国产另类| 欧美一区二区三区在| 久久精品亚洲热| 另类成人小视频在线| 亚洲成人自拍视频| 99re热这里只有精品视频 | 亚洲欧洲精品一区二区精品久久久| 欧美激情免费观看| 日韩亚洲欧美一区| 亚洲自拍偷拍福利| 久久久久国产精品人| 欧美1区3d| 欧美视频在线免费| 国产自产女人91一区在线观看| 尤物在线观看一区| 99精品欧美一区二区蜜桃免费| 中文在线不卡视频| 久久精品一区蜜桃臀影院| 欧美xart系列在线观看| 亚洲另类在线一区| 欧美一级成年大片在线观看| 久久亚洲影院| 欧美午夜性色大片在线观看| 国产一区二区日韩精品| 亚洲精品欧美一区二区三区| 亚洲一区在线看| 欧美www视频在线观看| 一本色道久久88综合亚洲精品ⅰ | 亚洲午夜激情免费视频| 久久久国产亚洲精品| 欧美日韩国产一区二区三区地区| 国产日韩视频| 亚洲无亚洲人成网站77777| 久久免费一区| 99精品久久| 另类av一区二区| 国产欧美一区二区三区在线看蜜臀| 亚洲国产精品ⅴa在线观看| 亚洲欧美综合v| 最新国产精品拍自在线播放| 欧美一级视频| 欧美午夜精品久久久久久浪潮| 1000部国产精品成人观看| 校园春色国产精品| 亚洲欧洲另类| 久久久精品性| 国产麻豆精品theporn| 夜夜爽99久久国产综合精品女不卡| 久久久99久久精品女同性| 日韩视频在线一区二区三区| 久久婷婷色综合| 国产视频一区免费看| 亚洲视频自拍偷拍| 亚洲国内精品在线| 久久永久免费| 精品白丝av| 久久午夜精品一区二区| 午夜国产精品视频|