• <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題目
            狠狠色婷婷久久综合频道日韩 | 国产色综合久久无码有码| 久久性生大片免费观看性| 久久久久久精品免费看SSS| 97久久精品无码一区二区天美| 久久久精品无码专区不卡| 久久婷婷五月综合色高清| 久久精品成人免费观看97| 国产一区二区三区久久| 亚洲精品无码久久久久AV麻豆| 欧美精品一区二区精品久久| 久久久久亚洲爆乳少妇无| 国产亚洲欧美精品久久久| 一97日本道伊人久久综合影院| 情人伊人久久综合亚洲| av午夜福利一片免费看久久| 97精品依人久久久大香线蕉97| 久久电影网| 国产精品一区二区久久精品无码 | 国内精品综合久久久40p| 久久久久亚洲AV无码专区网站 | 精品久久久久久国产| 久久无码人妻精品一区二区三区| 国产V综合V亚洲欧美久久| 久久人人爽人人爽人人片av麻烦| 国产免费福利体检区久久| 国产一久久香蕉国产线看观看| 国产精品一区二区久久不卡| 久久人妻少妇嫩草AV无码专区 | 久久久久久久综合狠狠综合| 国产精品久久久久久久久久免费| 久久被窝电影亚洲爽爽爽| 日产精品99久久久久久| 丁香色欲久久久久久综合网| 狠狠色丁香久久婷婷综合_中| 综合久久一区二区三区 | 国产高清国内精品福利99久久| 国产69精品久久久久9999| 久久久久国产| 久久久亚洲裙底偷窥综合| 一本色道久久综合亚洲精品|