• <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題目
            色综合合久久天天综合绕视看| 欧美综合天天夜夜久久| 伊人久久综合无码成人网| 国产精品久久久久AV福利动漫| 国产精品99久久久久久www| 久久亚洲日韩看片无码| 久久成人国产精品二三区| 久久久综合香蕉尹人综合网| 久久精品亚洲中文字幕无码麻豆 | 欧美精品国产综合久久| …久久精品99久久香蕉国产| 日韩亚洲国产综合久久久| 国产亚洲欧美成人久久片| 伊人色综合九久久天天蜜桃 | 伊人热热久久原色播放www| 亚洲成人精品久久| 一本色道久久综合亚洲精品| 伊人久久国产免费观看视频| 国产巨作麻豆欧美亚洲综合久久| 久久久噜噜噜www成人网| 久久精品亚洲AV久久久无码| 久久天天日天天操综合伊人av| 精品久久久久久久| 亚洲AV成人无码久久精品老人| 一本大道加勒比久久综合| 少妇久久久久久被弄高潮| 2019久久久高清456| 亚洲精品乱码久久久久久不卡| 99久久伊人精品综合观看| 久久婷婷国产麻豆91天堂| 久久av无码专区亚洲av桃花岛| 久久综合亚洲鲁鲁五月天| 欧美成人免费观看久久| 麻豆亚洲AV永久无码精品久久| 伊人久久无码中文字幕| 久久亚洲AV无码精品色午夜麻豆| 久久久久亚洲av成人无码电影| 合区精品久久久中文字幕一区 | 久久无码专区国产精品发布| 一级做a爰片久久毛片看看| 伊色综合久久之综合久久|