题意:求在平面上 任意两点连线,原点到这个点的距离小于d的点对有多少个，n=200000;
解: 以原点为圆心做一个半径为d的圆，我们知道圆内的点和园内以外的点的连线都是小于d的还有，圆内和园内的点联线也是小于d的,那么需要处理的是圆外和圆外的点。
以每个圆外的点 向圆做切线 然后我们知道有绿色点区域是允许和他搭配的
那么这些点有一个共同特点 那就他们和圆的切线都在 那个点切点的一侧，这样我们就让每个点 转化为两个切点，然后按照极角排序，求出那些不想交区间就是不合法的
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxn=*;
const double eps=0.000000000001;
const double PI=acos(-1.0);
struct Point
{
double x,y;
Point(double cx=,double cy=)
{
x=cx; y=cy;
}
};
struct Circle{
Point c;
double r;
Circle(Point c,double r):c(c),r(r){}
Point point(double a)
{
return Point(c.x+cos(a)*r,c.y+sin(a)*r);
}
};
int dcmp(double a)
{
if(fabs(a)<eps)return ;
return a<?-:;
}
double angle(Point v)
{
return atan2(v.y,v.x);
}
Point operator -(Point A, Point B)
{
return Point(A.x-B.x,A.y-B.y);
}
double Length(Point c)
{
return sqrt(c.x*c.x+c.y*c.y);
}
Point Rotate(Point A, double rad)
{
return Point(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
void getTangents(Point p, Circle C,double &A, double &B)
{
Point u=p;
double dist=Length(u);
if(dcmp(dist-C.r)==){
double a=atan2(p.y,p.x);
if(a<){
B=A=a+PI*;
}else A=B=a;
}else{
double ang=acos(C.r/dist);
Point t=Rotate(u,ang);
double a=atan2(t.y,t.x);
if(a<)
{
A=a+PI*;
B=a-ang*+PI*;
}else{
A=a;
B=a-ang*;
if(B<)B+=PI*;
}
}
}
Point P[maxn];
struct Elem
{
double L,R;
int cL,cR;
bool operator <(const Elem &rhs)const
{
return cL<rhs.cL||(cL==rhs.cL&&cR<rhs.cR);
}
}E[maxn];
double JJ[maxn*];
int C[maxn*];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int v,int n)
{
if(x<=)return ;
while(x<=n)
{
C[x]+=v;
x+=lowbit(x);
}
}
int sum(int x)
{
int ans=;
while(x>)
{
ans+=C[x];
x-=lowbit(x);
}
return ans;
}
int main()
{
int n;
double d;
while(scanf("%d%lf",&n,&d)==)
{
LL ge=,nu=,cc=;
Circle c(Point(,),d);
for(int j=; j<n; j++)
{
scanf("%lf%lf",&P[nu].x,&P[nu].y);
if(dcmp(Length(P[nu])-d)<)
{
ge++;
}
else
{
getTangents(P[nu],c,E[nu].L,E[nu].R);
if(E[nu].L>E[nu].R)swap(E[nu].L,E[nu].R);
JJ[cc++]=E[nu].L;JJ[cc++]=E[nu].R;
nu++;
}
}
sort(JJ,JJ+cc);
ge=;
for(int i=; i<cc; i++)
{
if(dcmp(JJ[i]-JJ[ge-])>)JJ[ge++]=JJ[i];
}
cc=ge;
for(int i=; i<=cc; i++)C[i]=;
for(int i=; i<nu; i++)
{
E[i].cL=upper_bound(JJ,JJ+cc,E[i].L)-JJ;
E[i].cR=upper_bound(JJ,JJ+cc,E[i].R)-JJ;
add(E[i].cL,,cc);
add(E[i].cR,-,cc);
}
sort(E,E+nu);
LL buhefa=;
for(int i=; i<nu; i++)
{
LL d1= sum(E[i].cR);
LL d2= sum(E[i].cL-);
buhefa+=d1-d2;
add(E[i].cL,-,cc);
add(E[i].cR,,cc);
}
LL nn=n;
LL ans=nn*(nn-)/-buhefa;
printf("%lld\n",ans);
}
return ;
}
/*
4 10
0 2
2 0
0 100
100 0
*/