计蒜之道 2017 程序设计大赛 – 计蒜客 复赛 B Windows 画图 几何、平面、枚举

计蒜之道 2017 程序设计大赛 - 计蒜客 复赛 B Windows 画图 几何、平面、枚举

Source

计蒜之道 2017 程序设计大赛 - 计蒜客 复赛 B Windows 画图

计蒜客 15967 Windows 画图

My Solution

题意：在一个m*m(1≤n≤80000,1≤m≤250)的平面内给出n条线段，然后给出q(1≤q≤62500)个询问，为点x，y最近被2条线段所经过，如果没有则输出0。

几何、平面、枚举

这里 8e4 * 250 == 2e7，刚好可以预处理出mp[x][y]表示最后一次经过的线段。

然后注意下精度问题即可，可能是向上修复精度，也可能是向下修复精度。

y = -1;

if(fabs(k*(j-xa) + ya*1.0 - double(int(k*(j-xa) + ya*1.0))) < EPS) y = int(k*(j-xa) + ya*1.0);

if(fabs(k*(j-xa) + ya*1.0 - double(int(k*(j-xa) + ya*1.0)) - 1) < EPS) y = int(k*(j-xa) + ya*1.0) + 1;

if(y < miny || y > maxy) continue;

mp[j][y] = i;

时间复杂度 O(n*m)

空间复杂度 O(m*m)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 80000 + 8, MAXM = 250 + 8;
const double EPS = 1e-6;

int mp[MAXM][MAXM];

int main()
{
    #ifdef LOCAL
    freopen("b.txt", "r", stdin);
    //freopen("b.out", "w", stdout);
    int T = 1;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    int n, m, i, j, xa, ya, xb, yb, y, miny, maxy;
    double k;
    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; i++){ scanf("%d%d%d%d", &xa, &ya, &xb, &yb); miny = min(ya, yb), maxy = max(ya, yb); if(xa > xb) swap(xa, xb), swap(ya, yb);

        if(xa == xb){
            for(j = miny; j <= maxy; j++){
                mp[xa][j] = i;
            }
            continue;
        }
        else k = (yb - ya)*1.0/(xb - xa);
        for(j = xa; j <= xb; j++){
            y = -1;
            if(fabs(k*(j-xa) + ya*1.0 - double(int(k*(j-xa) + ya*1.0))) < EPS) y = int(k*(j-xa) + ya*1.0);
            if(fabs(k*(j-xa) + ya*1.0 - double(int(k*(j-xa) + ya*1.0)) - 1) < EPS) y = int(k*(j-xa) + ya*1.0) + 1;
            if(y < miny || y > maxy) continue;
            mp[j][y] = i;
        }
    }
    int q;
    scanf("%d", &q);
    while(q--){
        scanf("%d%d", &xa, &ya);
        printf("%dn", mp[xa][ya]);
    }



    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx