• <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年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217844
            • 排名 - 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 閱讀(493) 評論(0)  編輯 收藏 引用 所屬分類: ACM題目
            无码精品久久久天天影视| 青青国产成人久久91网| 亚洲国产精品综合久久一线| 欧美亚洲另类久久综合婷婷| 亚洲午夜久久久久久噜噜噜| 99久久国产综合精品网成人影院 | 国产成人精品久久亚洲高清不卡 | 狠狠人妻久久久久久综合蜜桃| 一本久久a久久精品综合香蕉| 国产成人精品久久免费动漫| 久久夜色撩人精品国产| 7777久久亚洲中文字幕| 久久青青草原精品国产软件 | 麻豆成人久久精品二区三区免费| 欧美日韩中文字幕久久伊人| 97精品依人久久久大香线蕉97| 99久久婷婷国产一区二区| 久久久噜噜噜久久中文福利| 性做久久久久久久久老女人| segui久久国产精品| 国产精品久久久天天影视| 久久国产色av免费看| 亚洲一级Av无码毛片久久精品| 91久久九九无码成人网站| 久久综合给久久狠狠97色| 久久狠狠爱亚洲综合影院| 亚洲欧美日韩久久精品| 久久精品成人影院| 久久99精品国产99久久6| 国产精品美女久久久| 久久久久成人精品无码中文字幕 | 2021国产精品午夜久久| 亚洲国产精品成人久久蜜臀| 亚洲精品国产自在久久| 欧美成a人片免费看久久| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区 | 三上悠亚久久精品| 久久一日本道色综合久久| MM131亚洲国产美女久久| 日韩精品久久久久久| 精品综合久久久久久88小说|