ACM模版

描述


题解

平面几何问题，遍历所有线段，不断更新坐标的状态即可。水题~~~

代码

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXM = 255;

int n, m, q;
int map[MAXM][MAXM];

struct node
{
    int x, y;
} A, B;

int main(int argc, const char * argv[])
{
    cin >> n >> m;

    for (int cnt = 1; cnt <= n; cnt++)
    {
        scanf("%d%d%d%d", &A.x, &A.y, &B.x, &B.y);
        if (A.x > B.x)
        {
            swap(A, B);
        }
        int tempX = B.x - A.x;
        int tempY = B.y - A.y;
        for (int i = A.x; i <= B.x; i++)
        {
            double y = A.y + (double)(i - A.x) * tempY / tempX;
            int y_ = (int)y;
            if (y == y_)
            {
                map[i][y_] = cnt;
            }
        }
    }

    cin >> q;
    while (q--)
    {
        scanf("%d%d", &A.x, &A.y);
        cout << map[A.x][A.y] << '\n';
    }

    return 0;
}