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

            先按題意找出最低點作為起始點,計算出起始向量。然后每次選擇左轉角度最小的點走。一定能走完 n 個點。

            /*************************************************************************
            Author: WHU_GCC
            Created Time: 2007-8-13 19:38:56
            File Name: pku1696.cpp
            Description: 
            ***********************************************************************
            */

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

            #define out(x) (cout << #x << ": " << x << endl)
            typedef 
            long long int64;
            const int maxint = 0x7FFFFFFF;
            const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
            template 
            <class T> void show(T a, int n) for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
            template 
            <class T> void show(T a, int r, int l) for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }

            typedef 
            struct point_t
            {
                
            int num;
                
            int x, y;
            }
            ;

            point_t 
            operator -(const point_t &a, const point_t &b)
            {
                point_t ret;
                ret.x 
            = a.x - b.x;
                ret.y 
            = a.y - b.y;
                
            return ret;
            }


            int64 det(
            const point_t &a, const point_t &b)
            {
                
            return int64(a.x) * b.y - int64(a.y) * b.x;
            }


            int64 dot(
            const point_t &a, const point_t &b)
            {
                
            return int64(a.x) * b.x + int64(a.y) * b.y;
            }


            double dist(const point_t &a)
            {
                
            return sqrt(double(a.x * a.x + a.y * a.y));
            }


            double angle(const point_t &a, const point_t &b)
            {
                
                
            double ret = acos(double(dot(a, b)) / (dist(a) * dist(b)));
                
            return det(a, b) > 0 ? ret : -ret;
            }


            const int maxn = 100;
            point_t p[maxn];
            int used[maxn];

            int main()
            {
                
            int ca;
                
            int n;
                
            for (scanf("%d"&ca); ca--;)
                
            {
                    scanf(
            "%d"&n);
                    
            for (int i = 0; i < n; i++)
                        scanf(
            "%d%d%d"&p[i].num, &p[i].x, &p[i].y);

                    
            int miny = 0x7FFFFFFF, mini;
                    
            for (int i = 0; i < n; i++)
                        
            if (p[i].y < miny)
                        
            {
                            miny 
            = p[i].y;
                            mini 
            = i;
                        }

                    memset(used, 
            0sizeof(used));
                    used[mini] 
            = 1;
                    
            int now = mini;
                    point_t now_vector;
                    now_vector.x 
            = 0;
                    now_vector.y 
            = p[mini].y;
                    printf(
            "%d", n);
                    
            for (int i = 1; i < n; i++)
                    
            {
                        printf(
            " %d", p[now].num);
                        
            double min_alpha = 1e200;
                        
            int minj;            
                        
            for (int j = 0; j < n; j++if (!used[j])
                        
            {
                            
            double t = angle(now_vector, p[j] - p[now]);
                            
            if (t < min_alpha)
                            
            {
                                min_alpha 
            = t;
                                minj 
            = j;
                            }

                        }

                        now_vector 
            = p[minj] - p[now];
                        now 
            = minj;
                        used[minj] 
            = 1;
                    }

                    printf(
            " %d\n", p[now].num);
                }

                
            return 0;
            }
            posted on 2007-08-13 20:46 Felicia 閱讀(496) 評論(0)  編輯 收藏 引用 所屬分類: 計算幾何
             
            国产成人香蕉久久久久| 日本人妻丰满熟妇久久久久久| 久久久久久亚洲AV无码专区| 久久A级毛片免费观看| 国产精品久久久久AV福利动漫| 久久精品国产亚洲AV嫖农村妇女| 99国产欧美久久久精品蜜芽| 狠狠色综合网站久久久久久久| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区| 一本一道久久a久久精品综合| 久久精品国产精品亚洲毛片 | 久久狠狠一本精品综合网| 伊人久久大香线蕉无码麻豆| 久久精品国产久精国产思思| 久久91精品综合国产首页| 久久婷婷五月综合97色| 欧美大战日韩91综合一区婷婷久久青草| 怡红院日本一道日本久久| 午夜欧美精品久久久久久久| 办公室久久精品| 久久中文骚妇内射| 尹人香蕉久久99天天拍| 青青草原综合久久大伊人精品| 久久人妻无码中文字幕| 久久强奷乱码老熟女| 亚洲欧美日韩精品久久| 久久精品www人人爽人人| 囯产极品美女高潮无套久久久 | 久久综合亚洲色一区二区三区| 久久香蕉国产线看观看乱码| 中文字幕人妻色偷偷久久| 久久综合久久伊人| 国产精品欧美久久久久天天影视| AV无码久久久久不卡网站下载| 狠狠色婷婷久久综合频道日韩| 欧美日韩成人精品久久久免费看| 国产日韩久久免费影院| 国产精品VIDEOSSEX久久发布 | 一本色道久久综合亚洲精品| 一级做a爰片久久毛片免费陪| 国产精品青草久久久久福利99|