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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
| #include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 500006
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define P 998244353
typedef long long ll;
int n , m , k;
#define cont( x1 , y1 , x2 , y2 , X1 , Y1 , X2 , Y2 ) ( x1 <= X1 && y1 <= Y1 && x2 >= X2 && y2 >= Y2 )
#define out( x1 , y1 , x2 , y2 , X1 , Y1 , X2 , Y2 ) ( x1 > X2 || y1 > Y2 || x2 < X1 || y2 < Y1 )
#define abs( a ) ( (a) > 0 ? (a) : ( -(a) ) )
struct node {
int d[2] , id;
void in( ) {
scanf("%d%d",d,d + 1);
}
} T[MAXN] , tmp;
int D;
inline bool cmp( node a , node b ) {
return a.d[D] < b.d[D];
}
int ch[MAXN][2] , lo[MAXN][2] , up[MAXN][2];
inline void pu( int rt ) {
int ls = ch[rt][0] , rs = ch[rt][1];
rep( d , 0 , 1 ) {
lo[rt][d] = up[rt][d] = T[rt].d[d];
if( ls ) lo[rt][d] = min( lo[rt][d] , lo[ls][d] ) , up[rt][d] = max( up[rt][d] , up[ls][d] );
if( rs ) lo[rt][d] = min( lo[rt][d] , lo[rs][d] ) , up[rt][d] = max( up[rt][d] , up[rs][d] );
}
}
int build( int l , int r , int d ) {
if( l > r ) return 0;
int mid = l + r >> 1;
D = d , nth_element( T + l , T + mid , T + r + 1 , cmp );
ch[mid][0] = build( l , mid - 1 , d ^ 1 ) , ch[mid][1] = build( mid + 1 , r , d ^ 1 );
pu( mid );
return mid;
}
ll dis( int x1 , int y1 , int x2 , int y2 ) {
return 1ll * ( x2 - x1 ) * ( x2 - x1 ) + 1ll * ( y2 - y1 ) * ( y2 - y1 );
}
ll calc( int u , node& t ) {
if( !u ) return 0;
int x = t.d[0] , y = t.d[1];
return max( max( dis( x , y , lo[u][0] , lo[u][1] ) , dis( x , y , lo[u][0] , up[u][1] ) ) , max( dis( x , y , up[u][0] , up[u][1] ) , dis( x , y , up[u][0] , lo[u][1] ) ) );
}
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>> > Q;
void que( int rt , node& t ) {
if( !rt ) return;
pair<ll,int> d = mp( dis( t.d[0] , t.d[1] , T[rt].d[0] , T[rt].d[1] ) , -T[rt].id );
if( Q.size() < k || d > Q.top() ) {
Q.push( d );
if( Q.size() > k ) Q.pop();
}
ll vl = calc( ch[rt][0] , t ) , vr = calc( ch[rt][1] , t );
if( vl >= vr ) {
if( Q.size() < k || Q.top().fi <= vl ) que( ch[rt][0] , t );
if( Q.size() < k || Q.top().fi <= vr ) que( ch[rt][1] , t );
} else {
if( Q.size() < k || Q.top().fi <= vr ) que( ch[rt][1] , t );
if( Q.size() < k || Q.top().fi <= vl ) que( ch[rt][0] , t );
}
}
void solve() {
cin >> n;
rep( i , 1 , n ) T[i].in( ) , T[i].id = i;
build( 1 , n , 0 );
int rt = ( 1 + n ) >> 1;
cin >> m;
rep( i , 1 , m ) {
tmp.in() , scanf("%d",&k);
while( !Q.empty() ) Q.pop();
que( rt , tmp );
printf("%d\n",-Q.top().se);
}
}
signed main() {
solve();
}
|
