DTOJ3302 星座

题目

题目描述

为了探索我们头顶那美丽的星空，伟大的C学给了我们一张星图，这张星图可以看做一个平面，其中包含了$n$n颗星星，每颗星星可以用平面上的一个点来表示，C学告诉我们这张星图中包含着多种神奇的$\alpha - \beta - \gamma$α−β−γ星座，这些星座在平面内构成了很多平行四边形，它们的都有一组边长为$\gamma$γ的对边平行于$x$x轴，且另一组对边平行于一斜率为$\frac{\beta}{\alpha}$αβ​的直线，现在C学给了我们若干组询问，每组询问包含$3$3个整数$\alpha,\beta,\gamma$α,β,γ，对于每组询问请你求出$x$x轴上方和下方中$\alpha - \beta - \gamma$α−β−γ星座的个数 (平行四边形不能与$x$x轴有相交的部分)

输入格式

第$1$1行$2$2个正整数$n,m$n,m表示星星的个数和询问的个数$(4 \leqslant n \leqslant 100,000,1 \leqslant m \leqslant 10)$(4⩽n⩽100,000,1⩽m⩽10)
第$2 \sim n+1$2∼n+1行每行$2$2个整数$x,y$x,y表示每颗星星的横纵坐标$(-1,000 \leqslant x,y \leqslant 1,000)$(−1,000⩽x,y⩽1,000)(数据保证不会有两颗星星在同一个位置)
第$n+2 \sim n+m+1$n+2∼n+m+1行每行$3$3个整数$\alpha,\beta,\gamma(1 \leqslant \alpha \leqslant 2,000,-2,000 \leqslant \beta \leqslant 2,000,1 \leqslant \gamma \leqslant 2,000)$α,β,γ(1⩽α⩽2,000,−2,000⩽β⩽2,000,1⩽γ⩽2,000)(当$\beta=0$β=0时，表示一条平行于 y轴的直线)

输出格式

输出共$m$m行
每行两个整数，表示$x$x轴上方满足条件星座个数和$x$x轴下方满足条件星座个数

样例

样例输入

8 1
1 1
2 1
1 2
2 2
1 -1
2 -1
1 -2
2 -2
1 0 1

样例输出

1 1

题解

看看这个坐标这么小，它不香吗？
我们用$v_{x,y}$vx,y​表示$(x,y)$(x,y)有没有点
算出有几条边平行$x$x轴，然后每条边选择左边那个点
算出斜率投影到$x$x轴上得到一个坐标，这个坐标相同的两条边可以组合成一个平行四边形（就是横截距相同而且斜率相同的直线只有一条）
附上代码：

#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,len1,len2,ans1,ans2,x[100010],y[100010],v[2010][2010];
double eps=1e-7,d1[100010],d2[100010];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]),v[x[i]+1000][y[i]+1000]=1;
	for(int i=1,a,b,c,s;i<=m;i++){
		ans1=ans2=len1=len2=s=0;
		scanf("%d%d%d",&a,&b,&c);
		for(int i=1;i<=n;i++) if(x[i]+c<=1000&&v[x[i]+1000+c][y[i]+1000]){
    		if(y[i]>0){
				d1[++len1]=x[i];
				if(b) d1[len1]-=1.0*a*y[i]/b;
			}
			else{
				d2[++len2]=x[i];
				if(b) d2[len2]-=1.0*a*y[i]/b;
			}
		}
		sort(d1+1,d1+1+len1),sort(d2+1,d2+1+len2);
		for(int i=2;i<=len1;++i)
			if(d1[i]-d1[i-1]<=eps) ++s;
			else ans1+=s*(s+1)/2,s=0;
		ans1+=s*(s+1)/2,s=0;
		for(int i=2;i<=len2;++i)
			if(d2[i]-d2[i-1]<=eps) ++s;
			else ans2+=s*(s+1)/2,s=0;
		printf("%d %d\n",ans1,ans2+s*(s+1)/2);
	}
}