• <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

            搜索

            •  

            積分與排名

            • 積分 - 217899
            • 排名 - 117

            最新評論

            閱讀排行榜

            評論排行榜

            Space Ant
            Time Limit:1000MS? Memory Limit:10000K
            Total Submit:113 Accepted:84

            Description
            The most exciting space discovery occurred at the end of the 20th century. In 1999, scientists traced down an ant-like creature in the planet Y1999 and called it M11. It has only one eye on the left side of its head and just three feet all on the right side of its body and suffers from three walking limitations:

            1. It can not turn right due to its special body structure.
            2. It leaves a red path while walking.
            3. It hates to pass over a previously red colored path, and never does that.

            The pictures transmitted by the Discovery space ship depicts that plants in the Y1999 grow in special points on the planet. Analysis of several thousands of the pictures have resulted in discovering a magic coordinate system governing the grow points of the plants. In this coordinate system with x and y axes, no two plants share the same x or y.
            An M11 needs to eat exactly one plant in each day to stay alive. When it eats one plant, it remains there for the rest of the day with no move. Next day, it looks for another plant to go there and eat it. If it can not reach any other plant it dies by the end of the day. Notice that it can reach a plant in any distance.
            The problem is to find a path for an M11 to let it live longest.
            Input is a set of (x, y) coordinates of plants. Suppose A with the coordinates (xA, yA) is the plant with the least y-coordinate. M11 starts from point (0,yA) heading towards plant A. Notice that the solution path should not cross itself and all of the turns should be counter-clockwise. Also note that the solution may visit more than two plants located on a same straight line.

            Input
            The first line of the input is M, the number of test cases to be solved (1 <= M <= 10). For each test case, the first line is N, the number of plants in that test case (1 <= N <= 50), followed by N lines for each plant data. Each plant data consists of three integers: the first number is the unique plant index (1..N), followed by two positive integers x and y representing the coordinates of the plant. Plants are sorted by the increasing order on their indices in the input file. Suppose that the values of coordinates are at most 100.

            Output
            Output should have one separate line for the solution of each test case. A solution is the number of plants on the solution path, followed by the indices of visiting plants in the path in the order of their visits.

            Sample Input

            2
            10
            1 4 5
            2 9 8
            3 5 9
            4 1 7
            5 3 2
            6 6 3
            7 10 10
            8 8 1
            9 2 4
            10 7 6
            14
            1 6 11
            2 11 9
            3 8 7
            4 12 8
            5 9 20
            6 3 2
            7 1 6
            8 2 13
            9 15 1
            10 14 17
            11 13 19
            12 5 18
            13 7 3
            14 10 16
            

            Sample Output

            10 8 7 3 4 9 5 6 2 1 10
            14 9 10 11 5 12 8 7 6 13 4 14 1 3 2
            

            Source
            Tehran 1999

            ?

            #include? < iostream >
            #include?
            < cmath >
            #include?
            < algorithm >
            using ? namespace ?std;

            const ? int ?MAXN? = ? 1000 ;
            const ? int ?INF? = ? 2000000000 ;

            struct ?XYDATA
            {
            ????
            int ?x,?y,?index;
            }
            ;

            int ?inorder(XYDATA?a,?XYDATA?b)
            {
            ????
            return ?a.y? < ?b.y? || ?(a.y? == ?b.y? && ?a.x? < ?b.x);
            }


            int ?cross(XYDATA?a,?XYDATA?b)
            {
            ????
            return ?a.x? * ?b.y? - ?a.y? * ?b.x;
            }


            double ?Cos(XYDATA?a,?XYDATA?b)
            {
            ????
            return ?(a.x * b.x + a.y * b.y)? / ?(sqrt(a.x * a.x + a.y * a.y)? * ?sqrt(b.x * b.x + b.y * b.y));
            }

            void ?Solve()
            {
            ????
            int ?n;
            ????
            int ?i,?j;
            ????
            int ? out [MAXN];
            ????
            int ?outSize? = ? 0 ?;
            ????
            bool ?mp[ 101 ][ 101 ];
            ????
            int ?t;
            ????
            double ?tmp;
            ????XYDATA?a[MAXN];
            ????XYDATA?v,?u;
            ????
            int ?beg;

            ????scanf(
            " %d " ,? & n);
            ????
            for ?(i = 0 ;?i < n;?i ++ )
            ????????scanf(
            " %d%d%d " ,? & a[i].index,? & a[i].x,? & a[i].y);
            ????
            ????sort(a,?a
            + n,?inorder);
            ????
            ????
            for ?(i = 0 ;?i < 101 ;?i ++ )
            ????????
            for ?(j = 0 ;?j < 101 ;?j ++ )
            ????????????mp[i][j]?
            = ? false ;

            ????v.x?
            = ?a[ 0 ].x;
            ????v.y?
            = ? 0 ;
            ????mp[a[
            0 ].x][a[ 0 ].y]? = ? true ;
            ????beg?
            = ? 0 ;
            ????
            out [outSize ++ ]? = ?a[ 0 ].index;
            ????
            for ?(i = 1 ;?i < n;?i ++ )
            ????
            {
            ????????
            bool ?isFind? = ? false ;
            ????????tmp?
            = ? - 2 ;
            ????????
            for ?(j = 0 ;?j < n;?j ++ )
            ????????????
            if ?(beg? != ?j? && ? ! mp[a[j].x][a[j].y])
            ????????????
            {
            ????????????????u.x?
            = ?a[j].x? - ?a[beg].x;
            ????????????????u.y?
            = ?a[j].y? - ?a[beg].y;
            ????????????????
            int ?cro? = ?cross(v,?u);
            ????????????????
            if ?(cro? >= ? 0 )????
            ????????????????
            {
            ????????????????????isFind?
            = ? true ;
            ????????????????????
            if ?(Cos(v,?u)? > ?tmp)?
            ????????????????????
            {
            ????????????????????????tmp?
            = ?Cos(v,?u);
            ????????????????????????t?
            = ?j;
            ????????????????????}

            ????????????????}

            ????????????}

            ????????
            if ?(isFind)
            ????????
            {
            ????????????v.x?
            = ?a[t].x? - ?a[beg].x;
            ????????????v.y?
            = ?a[t].y? - ?a[beg].y;
            ????????????mp[a[t].x][a[t].y]?
            = ? true ;
            ????????????beg?
            = ?t;
            ????????????
            out [outSize ++ ]? = ?a[t].index;
            ????????}

            ????????
            else ?
            ????????
            {
            ????????????
            break ;
            ????????}

            ????}

            ????printf(
            " %d " ,?outSize);
            ????
            for ?(i = 0 ;?i < outSize;?i ++ )
            ????????printf(
            " ?%d " ,? out [i]);
            ????printf(
            " \n " );
            }



            int ?main()
            {
            ????
            int ?n;

            ????scanf(
            " %d " ,? & n);

            ????
            while ?(n -- ? != ? 0 )
            ????
            {
            ????????Solve();
            ????}

            ????
            return ? 0 ;
            }
            posted on 2006-09-27 13:54 閱讀(544) 評論(0)  編輯 收藏 引用 所屬分類: ACM題目
            久久久受www免费人成| 国产高潮国产高潮久久久91 | 亚洲国产成人久久综合碰| 久久久中文字幕日本| 亚洲精品无码成人片久久| 久久国产亚洲高清观看| 很黄很污的网站久久mimi色 | 亚洲精品无码久久毛片| 色欲综合久久中文字幕网| 久久免费小视频| 亚洲色大成网站www久久九| 精品国产乱码久久久久久1区2区 | 欧美一区二区久久精品| 亚洲国产精品无码久久SM| 久久99国产亚洲高清观看首页| 久久亚洲色一区二区三区| 久久国产精品99精品国产| 欧美国产精品久久高清| 成人国内精品久久久久一区| 久久久久亚洲av成人无码电影| 久久亚洲日韩精品一区二区三区| 久久国产成人精品国产成人亚洲| 久久久一本精品99久久精品66| 无码人妻久久一区二区三区蜜桃 | 久久精品国产99久久无毒不卡| 久久97久久97精品免视看秋霞| 国产亚洲精久久久久久无码| 香蕉久久夜色精品国产2020| 色综合久久88色综合天天| 无遮挡粉嫩小泬久久久久久久| 亚洲日本久久久午夜精品| 人妻系列无码专区久久五月天| 国产精品激情综合久久| 久久99国产精品久久99| 99久久国产热无码精品免费| 日韩精品久久无码人妻中文字幕| 欧美激情精品久久久久久久| 日本久久中文字幕| 欧美日韩久久中文字幕| 2021国内久久精品| 久久精品国产2020|