Description：

给出平面上 $n$ 个整点和一个数 $K$ ， $m$ 次询问每次给出一个点，询问以这个点为左下点底边平行于 $x$ 轴的正三角形最小整边长。

$1\leqslant n\leqslant 10^5$

Solution：

首先不难发现可以二分，但是直接二分复杂度是错的，因为二维数点复杂度就是 $O(n)$ ，于是我们可以把所有询问放在一起二分，也就是说先把值域补成 $2$ 的幂，然后每次二维数点就行了，由于这题是统计正三角形内点的个数因此要转坐标系。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,k;

#define MAXN 300010

struct point

{

	double x,y;

}p[MAXN];

struct query

{

	double x,y;

	int l,r;

}q[MAXN];

bool cmp_p(point a,point b){return (a.x == b.x ? a.y < b.y : a.x < b.x);}

#define N 100000000

namespace ST

{

	struct node

	{

		int lc,rc;

		int sum;

	}t[MAXN * 30];

	int ptr = 0,root;

	int newnode(){return ++ptr;}

	#define mid ((l + r) >> 1)

	void insert(int &rt,int p,int l,int r)

	{

		if(rt == 0)rt = newnode();

		t[rt].sum += 1;

		if(l == r)return;

		if(p <= mid)insert(t[rt].lc,p,l,mid);

		else insert(t[rt].rc,p,mid + 1,r);

		return;

	}

	int query(int rt,int L,int R,int l,int r)

	{

		if(rt == 0)return 0;

		if(L <= l && r <= R)return t[rt].sum;

		int res = 0;

		if(L <= mid)res += query(t[rt].lc,L,R,l,mid);

		if(R > mid)res += query(t[rt].rc,L,R,mid + 1,r);

		return res;

	}

	void clear(int &rt,int l,int r)

	{

		if(rt == 0)return;

		if(l != r)clear(t[rt].lc,l,mid),clear(t[rt].rc,mid + 1,r);

		t[rt].sum = t[rt].lc = t[rt].rc = 0;

		rt = 0;

		return;

	}

}

struct CNT

{

	struct poi

	{

		double x,y;

		int tp;

		bool operator < (const poi &b)const{return (x == b.x ? y < b.y : x < b.x);}

	}s[MAXN * 5];

	int pnum;

	int ans[MAXN];

	double v[MAXN];

	int vcnt;

	void addp(double x,double y){v[++vcnt] = y;s[++pnum] = (poi){x,y,0};return;}

	void addq(double x,double y,int id){s[++pnum] = (poi){x,y,id};return;}

	void calc()

	{

		v[++vcnt] = 1000000000;v[++vcnt] = -1000000000;

		memset(ans,0,sizeof(ans));

		sort(v + 1,v + 1 + vcnt);

		vcnt = unique(v + 1,v + 1 + vcnt) - v - 1;

		sort(s + 1,s + 1 + pnum);

		for(int i = 1;i <= pnum;++i)s[i].y = upper_bound(v + 1,v + 1 + vcnt,s[i].y) - v - 1;

		for(int i = 1;i <= pnum;++i)

		{

			if(s[i].tp == 0)ST::insert(ST::root,s[i].y,0,N);

			else 

			{

				int res = ST::query(ST::root,0,min(s[i].y,1.0 * N),0,N);

				if(s[i].tp > 0)ans[s[i].tp] += res;

				else ans[-s[i].tp] -= res;

			}

		}

		ST::clear(ST::root,0,N);

		ST::ptr = 0;vcnt = pnum = 0;

		return;

	} 

}c1,c2;

int main()

{

	scanf("%d%d%d",&n,&m,&k);

	for(int i = 1;i <= n;++i)scanf("%lf%lf",&p[i].x,&p[i].y);

	for(int i = 1;i <= m;++i)

	{

		scanf("%lf%lf",&q[i].x,&q[i].y);

		q[i].l = 0;q[i].r = 1073741823;

	}

	int len = 1073741824;

	while(len != 1)

	{

		for(int i = 1;i <= n;++i)

		{

			c1.addp(p[i].x - 1.0 / sqrt(3) * p[i].y,p[i].y);

			c2.addp(p[i].x + 1.0 / sqrt(3) * p[i].y,p[i].y);

		}

		for(int i = 1;i <= m;++i)

		{

			int mi = (q[i].l + q[i].r) / 2;

			c1.addq(q[i].x - 1.0 / sqrt(3) * q[i].y - 0.0001,q[i].y + 1.0 * mi / 2 * sqrt(3),-i);

			c1.addq(q[i].x - 1.0 / sqrt(3) * q[i].y - 0.0001,q[i].y - 1,i);

			c2.addq(q[i].x + mi + 1.0 / sqrt(3) * q[i].y,q[i].y + 1.0 * mi / 2 * sqrt(3),i);

			c2.addq(q[i].x + mi + 1.0 / sqrt(3) * q[i].y,q[i].y - 1,-i);

		}

		c1.calc();c2.calc();

		for(int i = 1;i <= m;++i)

		{

			int mi = (q[i].l + q[i].r) / 2;

			if(c2.ans[i] + c1.ans[i] >= k)q[i].r = mi;

			else q[i].l = mi + 1;

		}

		len = len >> 1;

	}

	for(int i = 1;i <= m;++i)printf("%d\n",(q[i].l == 1073741823 ? -1 : q[i].l));

	return 0;

}