洛谷P5545 炸弹攻击2

传送门

题目背景

还记得那款题为炸弹攻击的塔防游戏吗？这款游戏出了续作，炸弹的威力大大加强了。

题目描述

游戏的地图是一个二维平面。JYY 的阵地位于xx轴下方，而所有的敌人目前都位于xx轴上方。

在 JYY 的阵地中有建有TT个激光塔和SS个发射源。其中第ii个防御塔T_iT
i
​
的坐标为(tx_i,ty_i)(tx
i
​
,ty
i
​
)，第ii个发射源S_iS
i
​
的坐标为(sx_i,sy_i)(sx
i
​
,sy
i
​
)。

地图上有DD个敌人，第ii个敌人D_iD
i
​
的坐标为(dx_i,dy_i)(dx
i
​
,dy
i
​
)。

两座激光塔可以相互连接形成能量墙。发射源朝向敌人发出的能量如果穿过了能量墙，可以得到巨大的加强而变为超级射线并瞬间消灭敌人。

JYY 想知道他有多少种可以可以发出超级射线的攻击方案。

具体来说，一个可以发出超级射线的攻击方案为一个由四个点组成的集合：{T_i,T_j,S_k,D_lT
i
​
,T
j
​
,S
k
​
,D
l
​
}，满足11\leq≤ii< i
​
T
j
​
和线段S_kD_lS
k
​
D
l
​
相交。

游戏设定保证在这TT++DD++SS个点中，不存在重点也不存在三点共线。

输入格式

第一行包含一个正整数DD；

接下来DD行，每行包含两个整数dx_i,dy_idx
i
​
,dy
i
​
，表示一个敌人的坐标；

第DD++11行包含一个整数SS；

接下来SS行，每行包含两个整数sx_i,sy_isx
i
​
,sy
i
​
，表示一个发射源的坐标；

第DD++SS++11行包含一个整数TT；

接下来TT行，每行包含两个整数(tx_i,ty_i)(tx
i
​
,ty
i
​
)，表示一个激光塔的坐标。

输出格式

输出一行一个整数，可以发出超级射线的攻击方案个数。

输入输出样例

输入 #1复制
3
1 12
10 30
30 10
1
10 -10
4
2 -11
9 -1
11 -1
15 -14
输出 #1复制
7

说明/提示

对于2020%的数据，满足D,S,TD,S,T\leq≤3030；

对于5050%的数据，满足D,S,TD,S,T\leq≤150150；

对于100100%的数据，满足11\leq≤D,S,TD,S,T\leq≤800800,dy_idy
i
​
00,sy_isy
i
​
,ty_ity
i
​
00，所有坐标绝对值不超过10^910
9
。

上代码：

#include
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 !up[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=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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49