HASH+二分查找,地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=2002
#include <stdio.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <stdlib.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <math.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int LEN = 1005;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int x;
int y;
}type;
type p[LEN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int cmp ( const void *a, const void *b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
type *c = ( type * )a;
type *d = ( type * )b;
int ans = c->x - d->x;
if ( ! ans )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
ans = c->y - d->y;
}
return ans;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int hash[LEN][LEN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void inith ( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for ( int j=0; j<n; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
hash[i][j] = 0;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int ser ( type *a, type *b, int n ) /**//*二分查找函数*/
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int c;
int l, r, mid;
l = 0;
r = n-1;
while ( l <= r )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
mid = ( l + r ) / 2;
if ( cmp ( a, &p[mid] ) >= 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
l = mid + 1;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
r = mid - 1;
}
}
if ( r<0 || cmp ( a, &p[r] ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return -1;
}
c = r;
l = 0;
r = n-1;
while ( l <= r )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
mid = ( l + r ) / 2;
if ( cmp ( b, &p[mid] ) >= 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
l = mid + 1;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
r = mid - 1;
}
}
if ( r<0 || cmp ( b, &p[r] ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return -1;
}
return c;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int check ( int s, type *a, type *b, int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
type c, d;
int disx, disy;
int k = ( a->x - b->x ) * ( a->y - b->y );
disx = abs ( a->x - b->x );
disy = abs ( a->y - b->y );
if ( k > 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
c.x = a->x - disy;
c.y = a->y + disx;
d.x = b->x - disy;
d.y = b->y + disx;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
c.x = a->x + disy;
c.y = a->y + disx;
d.x = b->x + disy;
d.y = b->y + disx;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( a->x >= c.x )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return 0;
}
int ans = ser ( &c, &d, n);
if ( ans == -1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return 0;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
hash[s][ans] = 1;
return 1;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int n;
int count;
while ( scanf ( "%d", &n ) != EOF && n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf ( "%d%d", &p[i].x, &p[i].y );
}
qsort ( p, n, sizeof ( type ), cmp );
count = 0;
inith ( n );
for ( i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for ( int j=i+1; j<n; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( ! hash[i][j] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
count +=check ( i, &p[i], &p[j], n );
}
}
}
printf ( "%d\n", count );
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
29 | 30 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
|
|