首页 > 代码库 > Circle 树状数组
Circle 树状数组
Description
You are given n points and two circles. The radius of the circle will be dynamical. Your task is to find how many points are under both circles at each time.
A point is under a circle iff the point is strictly inside the circle or on the border of the circle.
Input Description
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases.
For each case, the first line contains two integers n, m.(1 <= n, m <= 100000) Means the number of points and the number of queries.
Next n lines each contains two integer x, y(0 <= x, y <= 80000), describe a point.
Next line contains four integers x1, y1, x2, y2 (0 <= x1, y1, x2, y2 <= 80000), describe the center of two circles.
Next m lines each line contains two integers R1, R2, describe the radius of two circles.(1 <= R1, R2 <= 100000)
For each case, the first line contains two integers n, m.(1 <= n, m <= 100000) Means the number of points and the number of queries.
Next n lines each contains two integer x, y(0 <= x, y <= 80000), describe a point.
Next line contains four integers x1, y1, x2, y2 (0 <= x1, y1, x2, y2 <= 80000), describe the center of two circles.
Next m lines each line contains two integers R1, R2, describe the radius of two circles.(1 <= R1, R2 <= 100000)
Output Description
For each query, output the number of points under both circles.
Sample Input
14 40 00 11 01 10 0 2 21 11 1010 110 10
Sample Output
0304
碰见很多这样的题目了，哎，以为是几何题，题解出来了才发现是树状数组，多做做，多总结
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<string> 6 #include<queue> 7 #include<cmath> 8 #include<vector> 9 10 using namespace std;11 12 #define mnx 10400013 #define ll long long14 #define inf 0x3f3f3f3f15 #define lson l, m, rt << 116 #define rson m+1, r, rt << 1 | 117 18 const int N = mnx;19 struct point{20 int x, y;21 point( int x = 0, int y = 0 ) : x(x), y(y) {}22 point operator - ( const point &b ) const {23 return point( x - b.x, y - b.y );24 }25 int length(){26 ll len = (ll)x * x + (ll)y * y;27 ll pt = sqrt( len );28 if( pt * pt < len ) pt++;29 return (int)pt;30 }31 bool operator < ( const point & b ) const{32 return x < b.x; 33 }34 }p[mnx], A, B;35 struct rad{36 int r1, r2, id;37 bool operator < ( const rad & b ) const{38 return r1 < b.r1;39 }40 }query[mnx];41 int bit[mnx];42 int sum( int x ){43 int ret = 0;44 while( x > 0 ){45 ret += bit[x]; x -= x & -x;46 }47 return ret;48 }49 void add( int i, int x ){50 while( i <= N ){51 bit[i] += x;52 i += i & -i;53 }54 }55 int ans[mnx];56 int main(){57 int cas;58 scanf( "%d", &cas );59 while( cas-- ){60 memset( bit, 0, sizeof(bit) );61 int n, m;62 scanf( "%d %d", &n, &m );63 for( int i = 0; i < n; i++ ){64 scanf( "%d %d", &p[i].x, &p[i].y );65 }66 scanf( "%d %d %d %d", &A.x, &A.y, &B.x, &B.y );67 for( int i = 0; i < n; i++ ){68 int dis1 = ( p[i] - A ).length();69 int dis2 = ( p[i] - B ).length();70 p[i] = point( dis1, dis2 );71 }72 sort( p, p + n );73 for( int i = 0; i < m; i++ ){74 scanf( "%d %d", &query[i].r1, &query[i].r2 );75 query[i].id = i;76 }77 sort( query, query + m );78 int j = 0;79 for( int i = 0; i < m; i++ ){80 while( j < n && p[j].x <= query[i].r1 ){81 add( p[j].y, 1 );82 j++;83 }84 ans[query[i].id] = sum( query[i].r2 );85 }86 for( int i = 0; i < m; i++ ){87 printf( "%d\n", ans[i] );88 }89 }90 return 0;91 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。