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

            poj 2187 Beauty Contest

               這個題我是按照discussion里面的說法,先求凸包,然后枚舉過的。因為開始先把求凸包算法里面的用到了數(shù)組名搞混了,無故wa了好
            多次。后面求凸包換了種算法過了。結(jié)果發(fā)現(xiàn)bug是搞混了數(shù)組名,然后把前面wa掉的代碼下載下來,改好之后也都過了。
               這個題主要是凸包算法需要處理有重復點,有多點共線之類的情況。那個按極角排序后,再求凸包的算法,對共點共線處理的不是很好,
            不過那個算法也過了這個題。有個直接按坐標排序后,再求上凸包和下凸包的算法,可以處理共點共線的情況。這個算法比較優(yōu)美啊,既不
            需要找y坐標最小的點,也不需要按極角排序,直接按坐標排序下,然后求凸包即可。
               這個算法的一點解釋:http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull
               另外,演算法筆記:http://www.csie.ntnu.edu.tw/~u91029/ConvexHull.html#a3上也有提到這個算法,我也是從這上面看到的。
            這個算法可以假設(shè)是Graham排序基準點在無限遠處,于是夾角大小的比較可以直接按水平坐標比較。

            代碼如下:
            #include <stdio.h>
            #include <algorithm>
            #include <math.h>
            using namespace std;
            struct Point
            {
                int x, y;
                bool operator<(const Point& p) const
                {
                    return x < p.x || x == p.x && y < p.y;
                }
            };
            Point pts[50100];
            Point pcs[50100];
            int nN;
            int nM;
            inline int SDis(const Point& a, const Point& b)
            {
                return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
            }

            double Det(double fX1, double fY1, double fX2, double fY2)
            {
                return fX1 * fY2 - fX2 * fY1;
            }

            double Cross(Point a, Point b, Point c)
            {
                return Det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
            }

            void Convex()
            {
                sort(pts, pts + nN);
             
                nM = 0;
                for (int i = 0; i < nN; ++i)
                {
                    while(nM >= 2 && Cross(pcs[nM - 2], pcs[nM - 1], pts[i]) <= 0)
                    {
                        nM--;
                    }
                    pcs[nM++] = pts[i];
                }
                for (int i= nN - 2, t = nM + 1; i >= 0; --i)
                {
                    while (nM >= t && Cross(pcs[nM - 2], pcs[nM - 1], pts[i]) <= 0)
                    {
                        nM--;
                    }
                    pcs[nM++] = pts[i];
                }
                nM--;//起點會被重復包含
            }

            int main()
            {
                while (scanf("%d", &nN) == 1)
                {
                    for (int i = 0; i < nN; ++i)
                    {
                        scanf("%d%d", &pts[i].x, &pts[i].y);
                    }
                    Convex();
                    int nMax = -1;
                    for (int i = 0; i < nM; ++i)
                    {
                        for (int j = i + 1; j < nM; ++j)
                        {
                            nMax = max(nMax, SDis(pcs[i], pcs[j]));
                        }
                    }
                    printf("%d\n", nMax);
                }
                
                return 0;
            }
               也可以用旋轉(zhuǎn)卡殼算法來求最遠點對,此題的完整代碼如下:
            #include <stdio.h> 
            #include <string.h>
            #include <math.h>
            #include <vector>
            #include <algorithm>
            using namespace std;

            struct Point
            {
                int x, y;
                bool operator < (const Point& p)const
                {
                    return x < p.x || x == p.x && y < p.y;
                }
            };

            double Det(double fX1, double fY1, double fX2, double fY2)
            {
                return fX1 * fY2 - fX2 * fY1;
            }

            double Cross(Point a, Point b, Point c)
            {
                return Det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
            }

            //輸入點集合,輸出凸包
            void Convex(vector<Point>& in, vector<Point>& out)
            {
                int nN = in.size();
                int nM = 0;

                sort(in.begin(), in.end());
                out.resize(nN);
                
                for (int i = 0; i < nN; ++i)
                {
                    while (nM >= 2 && Cross(out[nM - 2], out[nM - 1], in[i]) <= 0)
                    {
                        nM--;
                    }
                    out[nM++] = in[i];
                }

                for (int i = nN - 2, t = nM + 1; i >= 0; --i)
                {
                    while (nM >= t && Cross(out[nM - 2], out[nM - 1], in[i]) <= 0)
                    {
                        nM--;
                    }
                    out[nM++] = in[i];
                }
                out.resize(nM);
                out.pop_back();//起始點重復
            }

            int SDis(Point a,Point b)
            {
                return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
            }

            int RC(vector<Point>& vp)
            {
                int nP = 1;
                int nN = vp.size();
                vp.push_back(vp[0]);
                int nAns = 0;
                for (int i = 0; i < nN; ++i)
                {
                    while (Cross(vp[i], vp[i + 1], vp[nP + 1]) > Cross(vp[i], vp[i + 1], vp[nP]))
                    {
                        nP = (nP + 1) % nN;
                    }
                    nAns = max(nAns, max(SDis(vp[i], vp[nP]), SDis(vp[i + 1], vp[nP + 1])));
                }
                vp.pop_back();
                return nAns;
            }

            int main()
            {
                int nN;
                vector<Point> inout;
                Point p;
                while (scanf("%d", &nN) == 1)
                {
                    in.clear(), out.clear();
                    while (nN--)
                    {
                        scanf("%d%d", &p.x, &p.y);
                        in.push_back(p);
                    }
                    Convex(inout);
                    
                    printf("%d\n", RC(out));
                }

                return 0;
            }
               關(guān)于旋轉(zhuǎn)卡殼的算法描述,網(wǎng)上有很多資料,比如,http://m.shnenglu.com/staryjy/archive/2010/09/25/101412.html 
            尤其關(guān)于這個求最遠點對的。

            posted on 2012-07-23 22:18 yx 閱讀(980) 評論(0)  編輯 收藏 引用 所屬分類: 計算幾何

            <2012年7月>
            24252627282930
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            導航

            統(tǒng)計

            公告

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            me

            好友

            同學

            網(wǎng)友

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久国产香蕉一区精品| 99久久777色| 久久久久99这里有精品10| 香蕉久久夜色精品国产2020| 日韩人妻无码精品久久免费一| 激情伊人五月天久久综合| 久久久99精品一区二区| 久久精品国产亚洲AV无码麻豆| 久久黄视频| 国产99精品久久| 国产69精品久久久久观看软件| 久久国产精品久久精品国产| 亚洲精品国产自在久久| 成人久久综合网| 久久精品国产亚洲AV久| 久久国产综合精品五月天| 69SEX久久精品国产麻豆| 久久久亚洲AV波多野结衣| 国产精品欧美久久久久天天影视 | 亚洲女久久久噜噜噜熟女| 国产精品99久久久久久www| 久久这里都是精品| 久久一区二区三区免费| 精品国产福利久久久| 久久久久人妻一区二区三区vr| 亚洲欧美精品一区久久中文字幕| 国产精品久久久久影院色| 久久婷婷五月综合色高清 | 色狠狠久久AV五月综合| 色婷婷综合久久久久中文字幕 | 国产精品久久久久久影院| 久久婷婷五月综合97色一本一本| 久久人人爽人人人人爽AV| 亚洲国产视频久久| 亚洲欧美日韩精品久久亚洲区| 国产精品激情综合久久| 久久播电影网| 久久人人超碰精品CAOPOREN| 国产精品亚洲综合专区片高清久久久| 精品久久久久久| 精品无码人妻久久久久久|