自动搬运

查看原文

来自洛谷，原作者为

	seajupiter **

搬运于2025-08-24 22:11:52，当前版本为作者最后更新于2019-12-05 17:14:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

算法：计算几何+双指针

首先，看数据范围可知，不能够去枚举每一条线段，两两判断是否相交。但是，本题较为特殊的是，满足所有敌人在x轴上方，所有发射源和激光塔在x轴下方。于是

• 分别对每个发射源进行处理
• 对于当前发射源S，把S到所有Di、Ti的向量按照极角排序
• 答案就是满足T1、T2夹角小于180度的（T1，D，T2）三元组的数量。可用Two Pointers思想求解。核心思想即为：对每一个左端点，找出可行区间的右端点。利用前缀和计算出T1为当前左端点，T2在当前区间内的方案数（从头到区间内每个T间D个数的累积和-从头到左端点D的个数累积和*区间内T的个数）
• 注意头尾可能相接构成方案，故可复制一倍做环状处理

最后，给出我个人的代码供大家参考

#include<bits/stdc++.h>
const double pi=3.1415926535;
using namespace std;
void read(int &x)
{
	char c=getchar();x=0;int f=1;
	while(!isdigit(c))f=c=='-'?-f:f,c=getchar();
	while(isdigit(c))x=x*10+c-'0',c=getchar();x*=f;
}
void read(long long &x)
{
	char c=getchar();x=0;int f=1;
	while(!isdigit(c))f=c=='-'?-f:f,c=getchar();
	while(isdigit(c))x=x*10+c-'0',c=getchar();x*=f;
}
const int N=1005;
int D,S,T;
struct point
{
	long long x,y;
	double angle;
	point(){}
	point(long long x0,long long y0){x=x0;y=y0;angle=atan2(y,x);};
	void init(){read(x);read(y);angle=atan2(y,x);}
	point operator-(const point &a)const{return point(x-a.x,y-a.y);}
}d[N],s[N],t[N];
typedef point vec;
long long cross(vec a,vec b){return a.x*b.y-a.y*b.x;}
const int onseg=0,onl=1,onr=-1;
int ccw(vec a,vec b)
{
	if(cross(a,b)>(long long)0)return onl;
	else if(cross(a,b)<(long long)0)return onr;
	else return onseg;
}
bool operator<(vec a,vec b){return a.angle>b.angle;}
long long ans;
struct ray
{
	vec vc;
	bool type;
}v[N<<2];
bool sign(long long x){return x>=0;}
bool cmp(ray a,ray b){return a.vc<b.vc;}
int sd[N<<2],st[N<<2],sum[N<<2];
void solve(point p)
{
	for(int i=1;i<=D;i++)v[i]={d[i]-p,0};
	for(int i=1;i<=T;i++)v[D+i]={t[i]-p,1};
	sort(v+1,v+1+D+T,cmp);
	for(int i=1;i<=D+T;i++)v[i+D+T]=v[i];
	for(int i=1;i<=(D+T)*2;i++)
	{
		st[i]=st[i-1];
		sd[i]=sd[i-1];
		sum[i]=sum[i-1];
		if(v[i].type)
		{
			st[i]++;
			sum[i]+=sd[i];
		}
		else sd[i]++;
	}
	for(int i=1,j=1;i<=D+T;i++)if(v[i].type)
	{
		j=max(j,i);
		while(j+1<i+D+T&&ccw(v[i].vc,v[j+1].vc)<=0)j++;
		ans+=sum[j]-sum[i]-sd[i]*(st[j]-st[i]);
	}
}
int main(){
	read(D);
	for(int i=1;i<=D;i++)d[i].init();
	read(S);
	for(int i=1;i<=S;i++)s[i].init();
	read(T);
	for(int i=1;i<=T;i++)t[i].init();
	for(int i=1;i<=S;i++)solve(s[i]);
	cout<<ans<<endl;
	return 0;
}

我写这道题时，因为找不到讲的比较详细的题解而走了许多弯路，花了两天才想出统计答案的办法，希望这篇题解能对读者有帮助。