计蒜客 window画图
在 Windows 的“画图”工具里,可以绘制各种各样的图案。可以把画图当做一个标准的二维平面,在其上先后绘制了 nn 条颜色互不相同的线段。
输出格式
输出 qq 行,每行一个整数,表示该位置最上面(最后绘制)的线段的编号。
若该点上不存在线段,请输出 00。
样例解释
样例对应题目描述中的图。
样例输入
5 8 2 5 5 2 5 2 3 8 8 4 1 4 2 2 5 8 8 7 4 1 4 3 4 5 2 6 4 3 5
样例输出
4 2 5 0
#include<iostream>
#include<map>
#include<stdio.h>
#include<cmath>
using namespace std;
int a[255][255];
int gcd(int a,int b)
{
if(b==0)return a;
return gcd(b,a%b);
}
int main()
{
int n;int m;
scanf("%d%d",&n,&m);
int cnt=1;
int x1,y1,x2,y2;int dx,dy;int GCD;int dirx,diry;
while(n--)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
dx=abs(x1-x2);dy=abs(y1-y2);
GCD=gcd(dx,dy);
dirx=x2>x1?1:-1;diry=y2>y1?1:-1;
dirx*=dx/GCD;diry*=dy/GCD;
int k=0;
while(abs(dirx*k)<=dx)
{
a[x1+dirx*k][y1+diry*k]=cnt;
k++;
}
cnt++;
}
int q;
scanf("%d",&q);int x,y;
while(q--)
{
scanf("%d%d",&x,&y);
printf("%d\n",a[x][y]);
}
return 0;
}