题目
题目描述
为了探索我们头顶那美丽的星空，伟大的C学给了我们一张星图，这张星图可以看做一个平面，其中包含了n颗星星，每颗星星可以用平面上的一个点来表示，C学告诉我们这张星图中包含着多种神奇的α−β−γ星座，这些星座在平面内构成了很多平行四边形，它们的都有一组边长为γ的对边平行于x轴，且另一组对边平行于一斜率为βα的直线，现在C学给了我们若干组询问，每组询问包含3个整数α,β,γ，对于每组询问请你求出x轴上方和下方中α−β−γ星座的个数 (平行四边形不能与x轴有相交的部分)
输入格式
第1行2个正整数n,m表示星星的个数和询问的个数(4⩽n⩽100,000,1⩽m⩽10)
第2∼n+1行每行2个整数x,y表示每颗星星的横纵坐标(−1,000⩽x,y⩽1,000)(数据保证不会有两颗星星在同一个位置)
第n+2∼n+m+1行每行3个整数α,β,γ(1⩽α⩽2,000,−2,000⩽β⩽2,000,1⩽γ⩽2,000)(当β=0时，表示一条平行于 y轴的直线)
输出格式
输出共m行
每行两个整数，表示x轴上方满足条件星座个数和x轴下方满足条件星座个数
样例
样例输入
1
2
3
4
5
6
7
8
9
10
| 8 1
1 1
2 1
1 2
2 2
1 -1
2 -1
1 -2
2 -2
1 0 1
|
样例输出
题解
看看这个坐标这么小，它不香吗？
我们用vx,y表示(x,y)有没有点
算出有几条边平行x轴，然后每条边选择左边那个点
算出斜率投影到x轴上得到一个坐标，这个坐标相同的两条边可以组合成一个平行四边形（就是横截距相同而且斜率相同的直线只有一条）
附上代码：
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
| #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);
}
}
|