• <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題目
            精品久久777| 久久免费线看线看| 久久久无码精品亚洲日韩软件| 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲 | 亚洲一区二区三区日本久久九| 久久精品夜色噜噜亚洲A∨| 欧美色综合久久久久久| 亚洲综合精品香蕉久久网| 久久久久夜夜夜精品国产| 欧美国产成人久久精品| 精品久久久久久久无码| 伊人色综合久久天天网| 国产国产成人久久精品| 久久超碰97人人做人人爱| 日韩影院久久| 久久精品亚洲福利| 久久免费视频网站| 久久狠狠高潮亚洲精品| 久久亚洲熟女cc98cm| 亚洲精品NV久久久久久久久久| 久久妇女高潮几次MBA| 无码8090精品久久一区| 久久久免费观成人影院| 久久高潮一级毛片免费| 91精品无码久久久久久五月天| 欧美一区二区三区久久综合 | 人妻少妇精品久久| 久久97久久97精品免视看秋霞| 久久99热国产这有精品| 国产精品久久久久久福利漫画| 久久国产热精品波多野结衣AV| 久久亚洲精品无码aⅴ大香| 久久亚洲熟女cc98cm| 久久久久久精品久久久久| 久久综合九色综合网站| 亚洲国产精品无码成人片久久| 久久久国产视频| 一本色综合网久久| 久久精品一本到99热免费| 99麻豆久久久国产精品免费| 69久久精品无码一区二区|