题目描述
身为课代表的她,下课总愿意帮老师发作业。老师的作业好多好多啊,一天
下来,她下课休息时间也无几了……
要是天花板上有一只激光炮该多好啊!把作业塞到激光炮里面,轰——一排
同学该都拿到作业了吧?如果激光炮装在了一排同学的中间,转来转去很不方便,
改装成同时往相对的两个方向发射不是更好吗?(嗯,抵消反冲力)这样发作业
该有多快啊,她能多省心啊!
可是因为激光炮太重了,转不动也移不动——嗯,没错,该在天花板上装上
轨道!嗯——这样,激光炮就可以平移了,可是……呃——还是不能转起来!
那只好把它移到最佳的位置了……可是,最佳的位置在哪里呢?
输入描述
一行一个整数 N(1≤N≤10)。
之后 N 行,每行两个数 X,Y(-10^9≤X,Y≤10^9,且 X≠0,Y≠0)描
述方向。如果把教室抽象成平面直角坐标系,那么当激光炮在坐标轴原点时,能
够射到点(X,Y)。
又一行一个整数 M(1≤M≤100000),教室里共有 M 个同学的书包。
之后 M 行,每行两个数 X,Y(-10^9≤X,Y≤10^9),依次描述每个同学
书包的位置。
再一行一个整数 Q(1≤Q≤100000),共有 Q 个询问。
之后 Q 行,每行两个数 X,Y(-10^9≤X,Y≤10^9),描述一组询问。
输出描述
对于每组询问给出的 X,Y,输出当激光炮移到(X,Y)时,能够把作业射
进多少个同学的书包。当然,如果在(X,Y)上有某个同学放着书包,激光炮
同样能把作业射进去。
输入样例
3
1 1
1 2
1 3
3
1 1
1 2
1 3
3 0 0
-1 0
-2 0
输出样例
3
1
1
数据范围
测试点编号 N= M≤ Q≤ X,Y∈
1 5 5 5
2 8 100 100 [-20,20]
3 8 200 200
4 8 500 500 [-50,50]
5 10 1000 1000 [-100,100] 6 10 5000 5000
7 10 100000 100000 [-1000,1000]
8 10 10000 10000 [-10000,10000] 9 10 100000 100000 10 10 [-10^9,10^9]
 
sol:令激光射到的点是xi,yi,书包是x,y询问时x0,y0,那么如果能射到,一定满足(x-x0)/(y-y0)=xi/yi,划一下式子就是xyi-xiy=x0yi-xiy0,显然前面的是可以预处理的,最多只有n*m条,用map存下来即可,注意判一下x0=x,y0=y即可
 
詹神题解

对平面进行哈希。考虑八皇后处理对角线的做法:用x+y和x-y来进行判重。
类似地,推广一下,我们可以用 k1x+k2y 的方法来进行判重。从各个点引出直
线,将原点代入方程检验即可。时间复杂度 O(N(M+Q))。
注意判断重点和重方向!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
ll s=; bool f=; char ch=' ';
while(!isdigit(ch)) {f|=(ch=='-'); ch=getchar();}
while(isdigit(ch)) {s=(s<<)+(s<<)+(ch^); ch=getchar();}
return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
if(x<) {putchar('-'); x=-x;}
if(x<) {putchar(x+''); return;}
write(x/); putchar((x%)+'');
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
const ll Base=;
const int N=;
int n,nn,m,Q;
struct Node
{
ll x,y;
inline bool operator==(const Node &tmp)const
{
return x*tmp.y==y*tmp.x;
}
}a[];
inline bool cmp(Node p,Node q)
{
if(p.y*q.y<) return (p.x*q.y<p.y*q.x);
else return (p.x*q.y>p.y*q.x);
}
map<ll,int>Zer,Map[N];
int main()
{
freopen("laser.in","r",stdin);
freopen("laser.out","w",stdout);
int i,j,x,y;
R(n);
for(i=;i<=n;i++)
{
R(a[i].x); R(a[i].y);
}
sort(a+,a+n+,cmp);
nn=unique(a+,a+n+)-a-;
R(m);
for(i=;i<=m;i++)
{
R(x); R(y);
Zer[x*Base+y]++;
for(j=;j<=nn;j++)
{
Map[j][x*a[j].y-y*a[j].x]++;
}
}
R(Q);
while(Q--)
{
R(x); R(y);
int ans=;
ans-=Zer[x*Base+y]*(nn-);
for(i=;i<=nn;i++) ans+=Map[i][x*a[i].y-y*a[i].x];
Wl(ans);
}
return ;
}

最新文章

  1. Sql Server系列:排序函数
  2. VS2010 水晶报表的使用
  3. MFC 启动其他程序 变相跳转
  4. maven快照版本和发布版本
  5. Ubuntu 14.10 下awk命令详解
  6. 【题解】A-B
  7. windows线程同步的总结
  8. L2,breakfast or lunch
  9. MyEclipse/Eclipse 使用图文详解
  10. 手工搭建基于ABP的框架(2) - 访问数据库
  11. e2e测试之Nightmare
  12. java小白设计模式之观察者模式
  13. Cocos2D旋转炮塔到指定角度(二)
  14. iOSAPP启动效果复杂动画之抽丝剥茧
  15. sql Server 创建临时表 嵌套循环 添加数据
  16. KMP字符串模式匹配算法(C++实现)
  17. windows git 上传
  18. Mysql InnoDB下的两种行锁
  19. PHP 缓存技术(一)
  20. H5上传图片之canvas

热门文章

  1. ORA-16401: archivelog rejected by RFS
  2. 浅谈.NET中的类型和装箱、拆箱原理
  3. springboot启动流程(八)ioc容器refresh过程(下篇)
  4. Cryptography -- 密码学
  5. Input system (输入子系统)
  6. navicat for oracle 导入xlsx文件提示无法打开xlsx文件
  7. sklearn特征工程
  8. python3使用ConfigParser从配置文件中获取列表
  9. python django uwsgi nginx安装
  10. 访问mapper方法提示invalid bound statement (not found)原因总结