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

            Why so serious? --[NKU]schindlerlee

            2010年02月13日星期六.sgu174 并查集+二叉搜索樹

            2010年02月13日星期六.sgu174
            sgu174:并查集+二叉搜索樹
            說說題意吧。就是每次給出兩個點,這兩個點代表一條線段,如果這一條線段能和已經存在的線
            段構成一個封閉多邊形,那么就輸出這是第幾條線段。

            很自然的能想到并查集,所差的就是為每一個點賦予一個唯一的編號。
            如果線性的查找已經處理過的點,那么就每次查詢的復雜度就是O(n).
            而有n個這樣的查詢。當n如此大的時候,n^2的算法顯然會超時。

            我們需要提高每次查詢的復雜度。
            其實很容易就能想到二叉搜索樹。不想寫的話可以直接使用stl中的map,map是紅黑樹的實現,如
            果不怕常數復雜度的話,這是一個很好的想法。

            還有就是并查集,并查集需要加上路徑壓縮,不然很容易超時。

             1 
             2 const int N = 400010;
             3 struct point_t {
             4     int x,y;
             5     point_t(){}
             6     point_t(int a,int b){x = a,y = b;}
             7 }a,b;一bool operator < (point_t a,point_t b)
             8 {
             9   if (a.x != b.x) {
            10       return a.x < b.x;
            11   }
            12   return a.y < b.y;
            13 }
            14 map<point_t,int> g;
            15 int n, p[N],rank[N];
            16 
            17 int findset(int x)
            18 {
            19   if (p[x] != x) {
            20       p[x] = findset(p[x]);
            21   }
            22   return p[x];
            23 }
            24 //http://www.shnenglu.com/schindlerlee
            25 bool unionset(int x,int y)
            26 {
            27   x = findset(x);
            28   y = findset(y);
            29   if (x == y) { return true; }
            30   if (rank[x] > rank[y]) {
            31       p[y] = x;
            32   } else if (rank[x] < rank[y]) {
            33       p[x] = y;
            34   } else if (rank[x] == rank[y]) {
            35       p[x] = y;
            36       rank[y]++;
            37   }
            38   return false;
            39 }
            40 
            41 int main()
            42 {
            43   int i,ia,ib;
            44   scanf("%d",&n);
            45   for (i = 0;i < N;i++) { p[i] = i; }
            46   for (i = 1;i <= n;i++) {
            47       scanf("%d%d%d%d",&a.x,&a.y,&b.x,&b.y);
            48       if ((ia = g[a]) == 0) { ia = g[a] = i << 1; } //from 1
            49       if ((ib = g[b]) == 0) { ib = g[b] = (i << 1+ 1; }
            50       if (unionset(ia,ib)) {
            51           printf("%d\n",i);
            52           break;
            53       }
            54   }
            55   if (i > n) {
            56       printf("0\n");
            57   }
            58   return 0;
            59 }
            60 


            posted on 2010-02-14 00:38 schindlerlee 閱讀(1568) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告

            99久久综合国产精品二区| 久久久久久久97| 久久亚洲春色中文字幕久久久| 国产亚洲精品自在久久| 四虎久久影院| 国产69精品久久久久9999| 久久伊人精品一区二区三区| 亚洲色婷婷综合久久| 思思久久99热免费精品6| 国内精品久久久久久99蜜桃| 久久亚洲国产成人影院| 久久久青草青青亚洲国产免观| 热99RE久久精品这里都是精品免费| 2021少妇久久久久久久久久| 少妇久久久久久被弄高潮| 久久AV高潮AV无码AV| 天天躁日日躁狠狠久久| 精品久久久久久中文字幕大豆网 | 久久国产热这里只有精品| 久久精品国产69国产精品亚洲| 日产精品久久久久久久| 中文字幕乱码人妻无码久久| 久久只有这精品99| 伊人久久大香线蕉综合Av| 国产91色综合久久免费| 久久精品国产欧美日韩| 欧美亚洲国产精品久久| 青青国产成人久久91网| 久久午夜福利电影| 蜜臀av性久久久久蜜臀aⅴ| 久久久精品人妻无码专区不卡| 久久经典免费视频| 久久无码精品一区二区三区| 久久久老熟女一区二区三区| 欧美麻豆久久久久久中文| 九九久久99综合一区二区| 99久久精品免费看国产一区二区三区| 久久精品中文闷骚内射| 无码国内精品久久人妻蜜桃| 欧美伊人久久大香线蕉综合69| 久久国产精品成人免费 |