### 题解

```#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 400010
#define ll long long

int n;
struct point{
ll x,y;
point operator+(const point &b){return (point){x+b.x,y+b.y};}
point operator-(const point &b){return (point){x-b.x,y-b.y};}
ll chaji(const point &b){return x*b.y-y*b.x;}
}P,Q,a[maxn];
double s[maxn][2],b[maxn];
double dis(point x,point y){return sqrt(1.0*(x.x-y.x)*(x.x-y.x)+1.0*(x.y-y.y)*(x.y-y.y));}
ll tree[maxn];
ll sum(int x){ll re=0;for(;x;x-=(x&-x))re+=tree[x];return re;}
double getangle(double x,double y,double z){return acos((x*x+y*y-z*z)/(2.0*x*y));}
struct par{
int x,y,type;par(int xx=0,int yy=0,int Type=0):x(xx),y(yy),type(Type){}
bool operator <(const par b)const{return x==b.x?(y<b.y):(x<b.x);}
}id[maxn];int t,tt;
ll work1(point &A,point &B)//同侧
{
ll re=0;t=tt=0;memset(tree,0,sizeof(tree));
for(int i=1;i<=n;i++)if((B-A).chaji(a[i]-A)>0)//只要一侧的点
{
t++;point P=a[i]; double PA=dis(P,A),PB=dis(P,B),AB=dis(A,B);
s[t][0]=getangle(PA,AB,PB);s[t][1]=getangle(PB,AB,PA);//用余弦公式计算角度
b[++tt]=s[t][0];b[++tt]=s[t][1];//记录下角度用于离散化
}
sort(b+1,b+tt+1);for(int i=1;i<=t;i++)//求二维偏序前的离散化
id[i].x=lower_bound(b+1,b+tt+1,s[i][0])-b,id[i].y=lower_bound(b+1,b+tt+1,s[i][1])-b;
}
const double Pi=acos(-1);
ll work2(point &A,point &B)//异侧
{
ll re=0;tt=0;memset(tree,0,sizeof(tree));
for(int i=1;i<=n;i++)
{
point P=a[i]; double PA=dis(P,A),PB=dis(P,B),AB=dis(A,B);
s[i][0]=getangle(PA,AB,PB);s[i][1]=getangle(PB,AB,PA);
if((B-A).chaji(P-A)>0)s[i][0]=Pi-s[i][0],s[i][1]=Pi-s[i][1];
b[++tt]=s[i][0];b[++tt]=s[i][1];
}
sort(b+1,b+tt+1);for(int i=1;i<=n;i++)
id[i].x=lower_bound(b+1,b+tt+1,s[i][0])-b,id[i].y=lower_bound(b+1,b+tt+1,s[i][1])-b,id[i].type=((B-A).chaji(a[i]-A)>0);