当前位置:首页 > 瞎暴力 > 计蒜客 Windows 画图

计蒜客 Windows 画图

在 Windows 的“画图”工具里,可以绘制各种各样的图案。可以把画图当做一个标准的二维平面,在其上先后绘制了 n 条颜色互不相同的线段。

按绘制的时间顺序,从先到后把线段依次编号为 1 到 n。第 i 条线段的两个端点分别为 (xa_i,ya_i) 和 (xb_i,yb_i),线段的粗细忽略不计。后绘制的线段不会改变之前绘制的线段的位置。

请写一个程序,回答 q 组询问,每组询问给出一个坐标 (x_i,y_i),你需要算出在这个点上最后绘制的线段编号。

输入格式

第一行包含两个正整数 n,m(1\leq n\leq 80000,1\leq m\leq 250),分别表示线段的数目以及坐标的最大取值(下面会具体说明)。

接下来 n 行,每行输入四个正整数 xa_i,ya_i,xb_i,yb_i (1\leq xa_i,ya_i,xb_i,yb_i\leq m, (xa_i,ya_i)\neq(xb_i,yb_i)),依次表示每条线段两个端点的坐标。

接下来一行,输入一个正整数 q(1\leq q\leq 62500),表示询问的组数。

接下来 q 行,每行输入两个正整数 x_i,y_i(1\leq x_i,y_i\leq m),分别表示每组询问的坐标。

输出格式

输出 q 行,每行一个整数,表示该位置最上面(最后绘制)的线段的编号。

若该点上不存在线段,请输出 0

样例解释

样例对应题目描述中的图。

样例输入

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

把线上的点都找出来  只有250*250 枚举就Ok

#include<stdio.h>
#include<algorithm>
using namespace std;

int gcd(int a,int b)
{
    return a%b==0?b:gcd(b,a%b);
}

int ma[255][255];

int main()
{
    int n,m,q,xx,yy,x1,x2,y1,y2,t;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);

        if(x1==x2)
        {
            if(y1>y2)
            {
                t=y1;y1=y2;y2=t;
            }
            for(int j=y1;j<=y2;j++)
                ma[x1][j]=i;
            continue;
        }
        if(y1==y2)
        {
            if(x1>x2)
            {
                t=x1;x1=x2;x2=t;
            }
            for(int j=x1;j<=x2;j++)
                ma[j][y1]=i;
            continue;
        }
        if(x1>x2)
        {
            t=x1;x1=x2;x2=t;
            t=y1;y1=y2;y2=t;
        }
        int dx=abs(x1-x2),dy=abs(y1-y2);
        int d=gcd(dx,dy);
        if(y1>y2) dy=-dy;

        while(x1<=x2)
        {
            ma[x1][y1]=i;
            x1+=dx/d;
            y1+=dy/d;
        }
    }
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d %d",&xx,&yy);
        printf("%d\n",ma[xx][yy]);
    }
    return 0;
}


除特别注明外,本站所有文章均为whppmy原创,转载请注明出处来自http://www.dengwenhuo.cn/?id=460

发表评论

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。