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

            gzwzm06

              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
              1 隨筆 :: 52 文章 :: 17 評論 :: 0 Trackbacks
            如果用過Hash,那么可能主要是算坐標的問題
              1 #include <cstdio>
              2 #include <cmath>
              3 #include <algorithm>
              4 using namespace std ;
              5 
              6 const int MAXN = 1101 ;
              7 const int KEY = 20011 ;
              8 const int MUL = 33 ;
              9 
             10 struct NODE
             11 {
             12     int x , y ;
             13     NODE *next ;
             14 
             15     NODE(){ next = NULL; }
             16 }hash[KEY] , gTemp[MAXN];
             17 
             18 int gPos ;
             19 
             20 struct POINT
             21 {
             22     int x, y ;
             23          
             24 }g_star[MAXN] ;
             25 
             26 int N ;
             27 
             28 bool cmp( const POINT& a, const POINT& b )
             29 {
             30     if ( a.x < b.x ){
             31         return true ;
             32     }
             33     else if ( a.x == b.x )
             34     {
             35         if ( a.y > b.y )
             36         {
             37             return true ;
             38         }
             39         else
             40             return false ;
             41     }
             42     return false ;
             43 }
             44 //計算哈希值
             45 int Cal( const int& sx, const int& sy )
             46 {
             47     int val , x = abs(sx), y = abs(sy) ;
             48     
             49     val = (x * MUL + y) % KEY ;
             50 
             51     return val ;
             52 }
             53 
             54 bool Find( const int& x, const int& y )
             55 {
             56     int pos = Cal( x, y ) ;
             57 
             58     NODE *ptr = hash[pos].next ;
             59 
             60     while ( ptr )
             61     {
             62         if ( ptr->x == x && ptr->y == y )
             63         {
             64             return true ;
             65         }
             66         ptr = ptr->next ;
             67     }
             68 
             69     return false ;
             70 }
             71 
             72 void Insert( const int& x, const int& y )
             73 {
             74     int pos = Cal( x, y ) ;
             75 
             76     NODE *ptr = &gTemp[gPos++] ;
             77 
             78     ptr->x = x ;
             79     ptr->y = y ;
             80     ptr->next = hash[pos].next ;
             81     hash[pos].next = ptr ;
             82 }
             83 //判斷是否能組成一個正方形而且不重復(fù)
             84 bool Judge( const POINT& a, const POINT& b )
             85 {
             86     int dx = ( b.x - a.x ) , dy = ( b.y - a.y ) ;
             87     int x1, y1, x2, y2 ;
             88     int flag = dx * dy ;
             89         
             90         dx = abs(dx) ;
             91         dy = abs(dy) ;
             92 
             93     if ( flag > 0 )
             94     {        
             95         x1 = a.x - dy , y1 = a.y + dx ;
             96         x2 = b.x - dy , y2 = b.y + dx ;
             97     }
             98     else {
             99         x1 = a.x + dy , y1 = a.y + dx ;
            100         x2 = b.x + dy , y2 = b.y + dx ;
            101     }
            102 
            103         if ( x1 <= a.x )
            104             return false ;
            105 
            106     if ( Find( x1, y1 ) && Find( x2, y2 ) )
            107         return true ;
            108     
            109     return false ;
            110 }
            111 
            112 void Init()
            113 {
            114     gPos = 0 ;
            115     for ( int i = 0 ; i < KEY ; ++i )
            116     {
            117         hash[i].next = NULL ;
            118     }
            119 }
            120 
            121 int main()
            122 {
            123     //freopen("in", "r", stdin) ;
            124 
            125     int i , j , count ;
            126 
            127     while ( scanf("%d", &N) && N != 0 )
            128     {
            129         Init() ;
            130         count = 0 ;
            131 
            132         for ( i = 0 ; i < N ; ++i )
            133         {
            134             scanf("%d %d", &g_star[i].x, &g_star[i].y) ;
            135             Insert( g_star[i].x, g_star[i].y ) ;
            136         }
            137                 //按左到右,上到下
            138                 sort(g_star, g_star + N, cmp) ;
            139                 
            140         for ( i = 0 ; i < N - 1 ; ++i )
            141         {
            142             for ( j = i + 1 ; j < N ; ++j )
            143             {            
            144                             if ( Judge(g_star[i], g_star[j]) )
            145                 count++ ;
            146                 
            147             }
            148         }
            149 
            150         printf("%d\n", count) ;
            151     }
            152 
            153     return 0 ;
            154 }
            155 


            posted on 2008-11-12 20:13 閱讀(289) 評論(0)  編輯 收藏 引用 所屬分類: Hash應(yīng)用
            久久久久久久久久久久中文字幕| 97超级碰碰碰碰久久久久| 亚洲精品午夜国产va久久| 亚洲欧美另类日本久久国产真实乱对白 | 国产精久久一区二区三区| 国产精品成人久久久久三级午夜电影| 国产精品熟女福利久久AV| 久久精品这里只有精99品| 久久青青草视频| 久久婷婷久久一区二区三区| 亚洲精品无码久久毛片| 久久99热国产这有精品| 久久久久久久女国产乱让韩| 99久久www免费人成精品| 久久精品卫校国产小美女| 91精品久久久久久无码| 无码人妻精品一区二区三区久久 | 久久精品国产99久久久香蕉| 久久久久亚洲av无码专区喷水| 美女久久久久久| 狠狠色丁香婷婷综合久久来来去 | 伊人色综合久久| 久久精品国产亚洲av麻豆色欲| 久久久久久久亚洲精品| 精品久久久久久久久中文字幕| 国产精品成人久久久| 久久精品国产色蜜蜜麻豆| 久久精品国产亚洲麻豆| 久久99精品久久久久久久久久| 伊人久久大香线蕉av一区| 久久人搡人人玩人妻精品首页| 99久久精品费精品国产| 久久久久中文字幕| 国产精品久久久久…| 精品免费久久久久久久| 久久久久亚洲AV无码麻豆| 亚洲精品无码久久千人斩| 亚洲AV无码久久| 久久国产精品一国产精品金尊| 亚洲国产精品18久久久久久| 久久无码人妻一区二区三区|