Gym 101480I Ice Igloos（思维乱搞）题解

题意：给个最多500 * 500的平面，有半径最多不为1的n个圆，现在给你1e5条线段，问你每条线段和几个圆相交，时限10s

思路：

因为半径<1，那么我其实搜索的范围只要在线段附近就好了。x1 == x2 或者 y1 == y2这个很好理解，不解释。如果是斜率> 0的，那么对于任意的x （x1 <= x < x2），那我的范围就是floor（yi）~ceil（yi+1），另一种斜率同理。然后我去数每一个格子有没有圆，能不能碰到我线段就行了。每个格子数完标记一下。可以偷个懒，标记为p，然后每次判是不是p，这样就省了每次都初始化。

题解虽然说最好规避sqrt，不过好像精度影响不大。

毒瘤的是输入，x1 > x2，y1 > y2。

代码：

#include<cmath>

#include<set>

#include<map>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include <iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = 500 + 10;

const int M = maxn * 30;

const ull seed = 131;

const int INF = 0x3f3f3f3f;

const int MOD = 1000000007;

double r[maxn][maxn], k;

int vis[maxn][maxn];

double a, b;

double getY(double x){

    return k * (x - a) + b;

}

bool check(double x, double y, double R){

    double dis = fabs(k * x - k * a + b - y) / sqrt(k * k + 1);

    if(dis <= R) return true;

    return false;

}

int main(){

    int n;

    int x1, y1, x2, y2, ans;

    memset(r, 0, sizeof(r));

    memset(vis, 0, sizeof(vis));

    scanf("%d", &n);

    for(int i = 1; i <= n; i++){

        int u, v;

        double l;

        scanf("%d%d%lf", &u, &v, &l);

        r[u][v] = l;

    }

    scanf("%d", &n);

    for(int p = 1; p <= n; p++){

        int up, down;

        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

        a = x1, b = y1;

        ans = 0;

        k = ((double)(y2 - y1)) / ((double)(x2 - x1));

        if(x1 == x2){

            if(y1 > y2) swap(y1, y2);

            for(int i = y1; i <= y2; i++)

                if(r[x1][i] != 0) ans++;

        }

        else if(y1 == y2){

            if(x1 > x2) swap(x1, x2);

            for(int i = x1; i <= x2; i++)

                if(r[i][y1] != 0) ans++;

        }

        else{

            if(x1 > x2){

                swap(x1, x2);

                swap(y1, y2);

            }

            if(k > 0){

                for(int i = x1; i < x2; i++){

                    up = (int)ceil(getY(i + 1));

                    down = (int)floor(getY(i));

                    if(i == x1) down = y1;

                    if(i == x2 - 1) up = y2;

                    for(int j = down; j <= up; j++){

                        if(r[i][j] > 0 && vis[i][j] != p && check(i, j, r[i][j])){

                            vis[i][j] = p;

                            ans++;

                        }

                        if(r[i + 1][j] > 0 && vis[i + 1][j] != p && check(i + 1, j, r[i + 1][j])){

                            vis[i + 1][j] = p;

                            ans++;

                        }

                    }

                }

            }

            else{

                for(int i = x1; i < x2; i++){

                    up = (int)ceil(getY(i));

                    down = (int)floor(getY(i + 1));

                    if(i == x1) up = y1;

                    if(i == x2 - 1) down = y2;

                    for(int j = down; j <= up; j++){

                        if(r[i][j] > 0 && vis[i][j] != p && check(i, j, r[i][j])){

                            vis[i][j] = p;

                            ans++;

                        }

                        if(r[i + 1][j] > 0 && vis[i + 1][j] != p && check(i + 1, j, r[i + 1][j])){

                            vis[i + 1][j] = p;

                            ans++;

                        }

                    }

                }

            }

        }

        printf("%d\n", ans);

    }

    return 0;

}

巴特西

Gym 101480I Ice Igloos（思维乱搞）题解

最新文章

热门文章