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

隨筆 - 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>
            影音先锋亚洲视频| 亚洲一区二区三区四区视频| 亚洲婷婷国产精品电影人久久| 亚洲国产电影| 久久久久高清| 久久久久久色| 国产一区二区无遮挡| 宅男噜噜噜66一区二区| 一区二区三区久久久| 欧美激情精品久久久久久大尺度| 久久久久综合一区二区三区| 国产欧美1区2区3区| 亚洲欧美日韩系列| 久久福利视频导航| 国产亚洲综合性久久久影院| 亚洲一区国产一区| 久久精品国产第一区二区三区| 欧美视频一区在线观看| 日韩一区二区福利| 亚洲一二三区视频在线观看| 欧美精品免费视频| 亚洲欧洲综合| 亚洲经典三级| 欧美激情第8页| 99国产精品| 午夜日韩在线观看| 国产欧美日韩另类一区| 欧美一区二区视频网站| 欧美专区第一页| 狠狠色狠狠色综合日日91app| 欧美在线电影| 欧美成人精品在线播放| 亚洲黄色一区| 欧美日韩的一区二区| 亚洲天堂偷拍| 久久久亚洲成人| 在线观看一区二区精品视频| 免费看成人av| 夜夜嗨av一区二区三区网页| 午夜日韩视频| 伊人久久综合| 欧美精品一线| 亚洲主播在线| 女人香蕉久久**毛片精品| 日韩亚洲欧美高清| 国产精品极品美女粉嫩高清在线| 午夜精品区一区二区三| 欧美jjzz| 亚洲欧美激情四射在线日 | 久久国产成人| 亚洲国产一区二区三区青草影视| 欧美日韩国产综合网| 亚洲欧美综合网| 欧美丰满高潮xxxx喷水动漫| 亚洲一区三区在线观看| 一区免费观看| 国产精品久久久久久久久借妻| 欧美一区二区视频在线观看2020| 亚洲国产精品ⅴa在线观看| 亚洲欧美视频在线| 亚洲国产精品一区二区三区| 国产精品激情电影| 免费日韩av片| 欧美一级网站| 夜夜嗨av一区二区三区网页| 免费91麻豆精品国产自产在线观看| 亚洲视频你懂的| 亚洲第一久久影院| 国产视频自拍一区| 欧美三级在线视频| 美国成人直播| 欧美一区国产二区| 亚洲视频中文字幕| 亚洲欧洲精品一区二区三区| 久久国产精品毛片| 亚洲欧美在线视频观看| 亚洲人成7777| 国内久久视频| 国产日韩欧美不卡在线| 国产精品地址| 欧美日韩国产精品一区二区亚洲| 久久亚裔精品欧美| 欧美一二区视频| 亚洲在线网站| 中国日韩欧美久久久久久久久| 亚洲激情网站| 亚洲高清视频中文字幕| 裸体女人亚洲精品一区| 久久成人这里只有精品| 亚洲欧美在线另类| 亚洲欧美偷拍卡通变态| 亚洲视频日本| 亚洲图片在线观看| 亚洲香蕉在线观看| 亚洲一区二区欧美| 一区二区三区高清在线观看| 亚洲乱码久久| 99riav久久精品riav| 日韩视频一区二区三区在线播放| 亚洲国产欧美日韩| 亚洲人成网站777色婷婷| 亚洲激精日韩激精欧美精品| 亚洲国产小视频在线观看| 亚洲欧洲精品天堂一级| 亚洲七七久久综合桃花剧情介绍| 亚洲清纯自拍| 夜夜嗨一区二区三区| 在线一区亚洲| 亚洲在线观看免费视频| 先锋影音一区二区三区| 久久国产日韩| 久久综合久色欧美综合狠狠| 狂野欧美激情性xxxx欧美| 欧美大片免费| 亚洲人线精品午夜| 一本大道久久a久久精二百| 国产精品99久久久久久人 | 亚洲天堂av在线免费| 亚洲欧美激情视频| 久久久福利视频| 欧美成人精品在线播放| 欧美日韩午夜精品| 国产精品自拍视频| **性色生活片久久毛片| 99re6这里只有精品| 午夜精品美女自拍福到在线 | 久久久久国产免费免费| 欧美成人蜜桃| 9人人澡人人爽人人精品| 亚洲女优在线| 免费看精品久久片| 国产精品国码视频| 伊人成人在线| 亚洲一区二区三区激情| 久久午夜精品| 99国产精品| 欧美在线影院| 欧美欧美在线| 韩国精品一区二区三区| 一本色道久久88综合亚洲精品ⅰ | 日韩一本二本av| 欧美一区2区视频在线观看 | 亚洲自拍啪啪| 久久综合九九| 亚洲色图自拍| 欧美jizzhd精品欧美喷水| 国产精品女主播| 亚洲人成77777在线观看网| 午夜亚洲伦理| 亚洲青色在线| 久久久久综合一区二区三区| 国产精品高清在线观看| 亚洲黄一区二区| 久久久久国色av免费观看性色| 亚洲开发第一视频在线播放| 久久成人国产精品| 国产精品毛片大码女人| 亚洲国产午夜| 另类成人小视频在线| 亚洲综合社区| 欧美性开放视频| 日韩一级成人av| 欧美va天堂va视频va在线| 亚洲欧美精品一区| 欧美日韩亚洲一区二区三区| 亚洲国产精品一区二区久| 久久精品三级| 亚洲男人的天堂在线观看| 欧美日韩国语| 亚洲精品一区二区在线观看| 免费91麻豆精品国产自产在线观看| 亚洲一区三区电影在线观看| 欧美日韩三级电影在线| 亚洲久久一区二区| 亚洲国产精品成人va在线观看| 久久久久久久久久久久久久一区| 国产欧美日韩精品专区| 性欧美长视频| 亚洲综合首页| 国产农村妇女毛片精品久久莱园子 | 久久精品国产亚洲一区二区| 99re这里只有精品6| 欧美成人免费网站| 亚洲国产精品综合| 欧美大尺度在线| 欧美+亚洲+精品+三区| 亚洲欧洲日夜超级视频| 欧美成人第一页| 老司机一区二区三区| 亚洲二区精品| 亚洲黄色有码视频| 欧美激情一区| av成人毛片| 一区二区三区高清视频在线观看| 欧美日韩你懂的| 亚洲一线二线三线久久久| 亚洲一级在线| 国产一区二区三区四区在线观看| 久久人人97超碰国产公开结果| 久久久av水蜜桃|