题解 P5545 【[JSOI2016]炸弹攻击2】

· · 题解

Portal

直接统计显然是不行的（n^4），我们必须得固定一个量，求出满足限制的其它三元组的个数。我选择固定发射源，并且将所有敌人与激光塔按照与当前发射源（之后称其为源点）的向量的倾角排序。

我们考虑符合条件的三元组个数。显然，因为激光塔全在 x 轴下方，敌人全在 x 轴上方，故在射线 (\text{源点},\text{敌人}) 两侧的所有激光塔对都可以与该敌人构成合法三元组。

但需要注意的是，当激光塔对与该射线无交点时，这个三元组是不合法的；稍加观察即可发现，有交点的充要条件是两激光塔的向量夹角 <\pi。（注意到它强调了没有三点共线的情况，这就使得很多边界情况不用处理。想要研究如何处理边界情况的，推荐这道题，尽管此种方法会在该题中因为常数过大而T掉）。

于是我们考虑再固定一个激光塔 j，则所有在其前方 \pi 范围内的其它激光塔都是合法的。我们可以通过 two-pointers 求出其前方最后一个合法激光塔 k。

在 two-pointers 的过程中，我们可以记录以当前节点为端点时的答案 sum、合法区间中的激光塔数 st、合法区间中的敌人数 se。

当一个激光塔进入区间时，st 增加，同时 sum 增加 se（该激光塔、j、se 中每个敌人，均构成一个三元组）。当一个敌人进入区间时，se 增加。当一个激光塔离开区间时，st 减少。当一个敌人离开区间时，se 减少，并且 sum 减少 st（理由同上）。

时间复杂度 O\Big(S(D+T)\log (D+T)\Big)，瓶颈在于排序。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi=acos(-1);
int E,T,B;
ll res;
struct Vector{
    int x,y;
    Vector(int X=0,int Y=0){x=X,y=Y;}
    friend Vector operator +(const Vector &u,const Vector &v){return Vector(u.x+v.x,u.y+v.y);}
    friend Vector operator -(const Vector &u,const Vector &v){return Vector(u.x-v.x,u.y-v.y);}
    friend Vector operator *(const Vector &u,const int &v){return Vector(u.x*v,u.y*v);}
    friend Vector operator /(const Vector &u,const int &v){return Vector(u.x/v,u.y/v);}
    friend ll operator &(const Vector &u,const Vector &v){return 1ll*u.x*v.y-1ll*u.y*v.x;}//cross times
    friend ll operator |(const Vector &u,const Vector &v){return 1ll*u.x*v.x+1ll*u.y*v.y;}//point times
    double operator !()const{return atan2(y,x);}
    friend bool operator <(const Vector &u,const Vector &v){return !u<!v;}
    void read(){scanf("%d%d",&x,&y);}
    void print(){printf("(%d,%d)",x,y);}
}ene[810],tow[810],bea[810];
pair<Vector,bool>p[1610];
int main(){
    scanf("%d",&E);
    for(int i=1;i<=E;i++)ene[i].read();
    scanf("%d",&B);
    for(int i=1;i<=B;i++)bea[i].read();
    scanf("%d",&T);
    for(int i=1;i<=T;i++)tow[i].read();
    for(int o=1;o<=B;o++){
        int m=0;
        for(int i=1;i<=T;i++)p[m++]=make_pair(tow[i]-bea[o],0);
        for(int i=1;i<=E;i++)p[m++]=make_pair(ene[i]-bea[o],1);
        sort(p,p+m);
        int sum=0,se=0,st=0,len=0;
        for(int j=0,k=0;j<m;){
            while(len<m&&(p[j].first&p[k].first)>=0){
                if(p[k].second==1)se++;
                else sum+=se,st++;
                len++,k=(k+1)%m;
            } 
            if(p[j].second==0)res+=sum;
            if(p[j].second==0)st--;
            else sum-=st,se--;
            j++,len--;
        }
    }
    printf("%lld\n",res);
    return 0;
}