DTOJ3302 星座

题目

题目描述

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

输入格式

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

输出格式

输出共$m$行
每行两个整数，表示$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}$表示$(x,y)$有没有点
算出有几条边平行$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);
    }
}