• <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>
            隨筆 - 87  文章 - 279  trackbacks - 0
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 218110
            • 排名 - 117

            最新評論

            閱讀排行榜

            評論排行榜

            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 閱讀(494) 評論(0)  編輯 收藏 引用 所屬分類: ACM題目
            亚洲精品国精品久久99热一| 久久人人爽人人爽人人片av高请| 国产高潮国产高潮久久久| 99蜜桃臀久久久欧美精品网站 | 久久丝袜精品中文字幕| 亚洲日本va午夜中文字幕久久| 一日本道伊人久久综合影| 久久99亚洲网美利坚合众国| 久久性生大片免费观看性| 亚洲色欲久久久综合网东京热| 久久精品国产99国产电影网| 最新久久免费视频| 欧美激情精品久久久久| 亚洲愉拍99热成人精品热久久| 狠狠色综合网站久久久久久久 | 久久久亚洲欧洲日产国码二区| 99久久成人18免费网站| 久久久久人妻一区二区三区vr| 色诱久久av| 久久97久久97精品免视看秋霞 | 性高朝久久久久久久久久| 久久99中文字幕久久| 久久婷婷国产综合精品| 久久天天躁狠狠躁夜夜avapp| 精品人妻伦九区久久AAA片69| 精品熟女少妇av免费久久| 亚洲AV无码久久精品蜜桃| 亚洲国产成人久久一区久久| 久久99精品久久久久久水蜜桃| 久久国产精品成人免费| 国产精品免费福利久久| 精品国产一区二区三区久久久狼| 色综合久久中文字幕综合网| 成人妇女免费播放久久久| 久久精品国产免费| 成人妇女免费播放久久久| 国内精品人妻无码久久久影院 | 9191精品国产免费久久| 欧美久久精品一级c片片| 久久91精品国产91久久户| 久久亚洲高清观看|