gzwzm06

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  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 //判断是否能组成一个正方形而且不重复
 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 阅读(278) 评论(0)  编辑 收藏 引用 所属分类: Hash应用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理