牛客练习赛60 F-几何带师 题解

题目传送门

题目大意： 给出一条线段 以及 个点，问从这 个点里面选出两个点，这两个点所在直线穿过 的方案数。

题解

考虑在 同侧的两点 ，假如 穿过 ，那么一定有 在 内或 在 内。

不妨设 在 内，那么一定满足 间一定满足 ，这个您随手画两条线段就能明白。

然后这个东西是个二维偏序问题，可以在 的时间内求出。

假如 在 异侧，那么就满足 和 。

移一下项，就是 和 ，依然是个二维偏序问题。

再说点细节，判断一个点在 哪一侧时，用两向量的叉积模长的正负性来判断（具体参考这里），求角度时，用三条边长度和余弦定理求出该角的 ，再用C++里的 函数求出其角度。

至于求二维偏序问题时，用的是简单的树状数组的做法。

代码如下：

#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];
void add(int x){for(;x<=maxn-10;x+=(x&-x))tree[x]++;}
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;
    sort(id+1,id+t+1);for(int i=1;i<=t;i++)re+=sum(id[i].y),add(id[i].y); return re;
}
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);
    sort(id+1,id+n+1);for(int i=1;i<=n;i++)if(id[i].type)re+=sum(id[i].y-1);else add(id[i].y); return re;
}

int main()
{
    scanf("%d %lld %lld %lld %lld",&n,&P.x,&P.y,&Q.x,&Q.y);
    for(int i=1;i<=n;i++)scanf("%lld %lld",&a[i].x,&a[i].y);
    printf("%lld",work1(P,Q)+work1(Q,P)+work2(P,Q));
}