Uoj 553 [unr 4] caproic acid set [computational geometry (points in circle → points in half plane)]

Title Description

Link

Two dimensional plane $n$ A little bit $(x_i,y_i)$,$Q$ Query distance $(0,z)$ Less than or equal to $R$ The number of points .

$n\le 12000,Q\le 10^6,|x_i|,|y_i|,|z_i|,R\le 10^9$

Topic analysis

$x^2+(y-z{)}^2\le R^2$

$x^2+y^2\le R^2-z^2+2yz$

$(x,y)\to (y,x^2+y^2)$

$y^{\prime }\le k{x}^{\prime }+b,k=2z,b=R^2-z^2$

The problem is to find the number of points under a line in the plane . Maintain the partial order relationship of each element under the slope determination , Asking can be based on $b$ Two points. .

$y-xk\le b$

If for a certain $k$, $x_1$ be better than $x_2$,$x_1<x_2$

be $y_1-x_{1}k\le y_2-x_{2}k$

namely $y_1-y_2\le k(x_1-x_2)*\frac{y_1-y_2}{x_1-x_2}\ge k$

Initially, it was assumed that $k=-\infty$,$k$ Gradually increase .

if $x_1=x_2$, be $y$ Small henggengyou .

So the initial sorting is based on $x$ For the first keyword ,$y$ For the second keyword .

Maintain such a partially ordered sequence , When $k$ Reach a certain value （$\le n(n-1)/2$ Secondary exchange ） when , Exchange the order of the elements .

If the swapped position is not adjacent , It means that they coincide with the exchange time of the intermediate elements , The operation of time coincidence can be switched arbitrarily . Cross out the preceding paragraph , fake .

This is equivalent to saying that if you change the exchange process of a selection sort in reverse order to $n(n-1)/2$ The exchange of sub random order can still be arranged in reverse order （ Obviously false , such as 1 2 3 4 If you swap (1,2),(1,3),(3,4), that 1 It's impossible to get to the end ）.

Therefore, when the exchange operation time is the same, it needs to ensure that it is a process similar to the selection sorting process , That is, operations with the same exchange time are sorted by the first dimension , And then sort by the second dimension .

Note that in this way, we still cannot guarantee that the adjacent two bits are exchanged each time , Because there may be multiple points distributed in two coordinates , But sorting is normal .

This section can be understood as a rotating scanning line , What needs to be considered is the case of multi-point collinearity and multi-point co coordinates .

The complexity of doing it directly is $O(n^2\log n+Q\log n)$

If the point is divided into several blocks , The size of the score block is $S$, Then the complexity becomes $O((S^2+Q)\log n\ast \frac{n}{S})$

$S=\sqrt{Q}$ Best when ,$O(n\sqrt{Q}\log n)$

PS： If the coordinates of the center of the circle can be taken arbitrarily , The problem becomes counting points in the three-dimensional half plane （ However, it seems that the author said that he would not ？ Manual formation ）

Code：

#include<bits/stdc++.h>
#define maxn 12005
#define maxq 1000005
#define LL long long
using namespace std;
char cb[1<<20],*cs,*ct;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<20,stdin),cs==ct)?0:*cs++)
template<class T>void read(T &a){
    
	char c;bool f=0;while(!isdigit(c=getc())) c=='-'&&(f=1);
	for(a=c-'0';isdigit(c=getc());a=a*10+c-'0'); f&&(a=-a);
}
inline void write(int x){
    
	if(x>=10) write(x/10);
	putchar(x%10+48);
}
const int S = 1000;
int n,Q,ans[maxq];
struct node{
    
	LL x,y; int id;
	void init1(){
    read(y),read(x),y=x*x+y*y;}// x<=1e9
	void init2(int i){
    read(x),read(y),y=y*y-x*x,x*=2,id=i;}// x<=2e9
	bool operator < (const node &p)const{
    return x^p.x?x<p.x:y<p.y;}
}a[maxn],q[maxq],b[maxn];
struct change{
    
	double t;
	int x,y;
	bool operator < (const change &p)const{
    return t==p.t?x^p.x?x<p.x:y<p.y:t<p.t;}
}C[S*S]; int Cn;
int pos[maxn];
void mdf(int i,int j){
    
	if(pos[i]>pos[j]) return;
	//assert(pos[j]-pos[i]==1); assert failed.
	swap(b[pos[i]],b[pos[j]]);
	swap(pos[i],pos[j]);
}
void solve(node *a,int n){
    
	sort(a+1,a+1+n);
	Cn=0;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++) if(a[i].x!=a[j].x){
    
			double t=1.0*(a[i].y-a[j].y)/(a[i].x-a[j].x); if(t>=q[Q].x) continue;
			C[++Cn]=(change){
    t,i,j};
		}
	sort(C+1,C+1+Cn);
	for(int i=1;i<=n;i++) pos[i]=i;
	for(int i=1,j=1;i<=Q;i++){
    
		for(;j<=Cn&&C[j].t<q[i].x;j++) mdf(C[j].x,C[j].y);
		int l=0,r=n,mid;
		while(l<r) mid=(l+r+1)>>1,a[mid].y-a[mid].x*q[i].x<=q[i].y?l=mid:r=mid-1;
		ans[q[i].id]+=l;
	}
}
int main()
{
    
	read(n),read(Q);
	for(int i=1;i<=n;i++) a[i].init1();
	for(int i=1;i<=Q;i++) q[i].init2(i);
	sort(q+1,q+1+Q);
	for(int i=1;i<=n;i+=S){
    
		for(int j=1;j<=S&&i+j-1<=n;j++) b[j]=a[i+j-1];
		solve(b,min(S,n-i+1));
	}
	for(int i=1;i<=Q;i++) write(ans[i]),putchar('\n');
}