Problem I: Ice Igloos

\[Time Limit: 10 s \quad Memory Limit: 512 MiB
\]

题意

给出\(n\)个圆，给出每个圆的坐标\(x\)、\(y\)以及半径\(r\)。

然后给出\(m\)条线段，问线段和几个圆相交。

思路

观察数据范围，\(0 \leq x，y \leq 500，0 < r < 1\)，既然数据范围这么小，就可以直接用\(500*500\)的数组存在该点的坐标。

\(\quad\)对于查询的线段，如果\(x1 == x2\)，那么就直接暴力查\([x1][y1]\)到\([x1][y2]\)内有圆的点的数量，如果\(y1==y2\)，也直接暴力查\([x1][y1]\)到\([x2][y1]\)内有圆的点的数量。

\(\quad\)对于存在斜率的线段，线段上的每一个\(x\)位置直接暴力他附近的点去查这些点是否存在圆，存在圆的话是否会和线段相交，如果这个线段是上升的，查询范围就是\([x][floor(x-1)-eps]\)到\([x][ceil(x+1)+eps]\)。如果线段是下降的，查询范围就是\([x][floor(x+1)-eps]\)到\([x][ceil(x-1)+eps]\)，然后特别判断一下线段开始和结束的\(x\)的查询范围，就可以了。

这样查询到的点不会特别大，是\(x2-x1\)的常数级，所以最后的复杂度就是\(O(M*500*k)\)。

/***************************************************************

    > File Name    : I.cpp

    > Author       : Jiaaaaaaaqi

    > Created Time : 2019年05月06日 星期一 17时14分40秒

 ***************************************************************/

#include <map>

#include <set>

#include <list>

#include <ctime>

#include <cmath>

#include <stack>

#include <queue>

#include <cfloat>

#include <string>

#include <vector>

#include <cstdio>

#include <bitset>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define  lowbit(x)  x & (-x)

#define  mes(a, b)  memset(a, b, sizeof a)

#define  fi         first

#define  se         second

#define  pii        pair<int, int>

#define  INOPEN     freopen("in.txt", "r", stdin)

#define  OUTOPEN    freopen("out.txt", "w", stdout)

typedef unsigned long long int ull;

typedef long long int ll;

const int    maxn = 5e2 + 10;

const int    maxm = 1e5 + 10;

const ll     mod  = 1e9 + 7;

const ll     INF  = 1e18 + 100;

const int    inf  = 0x3f3f3f3f;

const double pi   = acos(-1.0);

const double eps  = 1e-8;

using namespace std;

int n, m;

int cas, tol, T;

long double a, b, c, k, l;

double vv[maxn][maxn];

int sgn(double x) {

    if(fabs(x) <= eps)	return 0;

    else	return x>0 ? 1 : -1;

}

void solve(int x1, int y1, int x2, int y2) {

    a = y2-y1;

    b = x1-x2;

	c = y1*(x2-x1)+x1*(y1-y2);

    double tmp = sqrt(a*a+b*b);

    a /= tmp;

    b /= tmp;

	c /= tmp;

    k = 1.0*(y2-y1)/(x2-x1);

    l = y1-k*x1;

}

int x1, y1, x2, y2;

double get(double x) {

    return k*x+l;

}

bool ok(int x, int y) {

    double r = vv[x][y];

    double dis = fabs(a*x+b*y+c);

    if(sgn(dis-r) <= 0)	return 1;

    else	return 0;

}

int main() {

    for(int i=0; i<=505; i++) {

        for(int j=0; j<=505; j++) {

            vv[i][j] = 0.0;

        }

    }

    scanf("%d", &n);

    double r;

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

        scanf("%d%d%lf", &x, &y, &r);

        vv[x][y] = r;

    }

    scanf("%d", &T);

    while(T--) {

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

        int ans = 0;

        if(x1 == x2) {

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

            for(int j=y1; j<=y2; j++) {

                if(vv[x1][j] != 0)	ans++;

            }

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

        } else if(y1 == y2) {

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

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

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

            }

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

        } else {

            if(x1 > x2 || (x1==x2&&y1>y2)) {

                swap(x1, x2);

                swap(y1, y2);

            }

            solve(x1, y1, x2, y2);

            if(y1 < y2) {

                int yy = ceil(get(x1+1)+eps);

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

                    for(int j=y1; j<=yy; j++) {

                        if(vv[i][j] <= eps)	continue;

                        if(ok(i, j))

                            ans++;

                    }

                }

                for(int x=x1+1; x<x2; x++) {

                    int yl = floor(get(x-1)-eps);

                    int yr = ceil(get(x+1)+eps);

                    for(int i=x; i<=x; i++) {

                        for(int j=yl; j<=yr; j++) {

                            if(vv[i][j] <= eps)	continue;

                            if(ok(i, j))

                                ans++;

                        }

                    }

                }

                yy = floor(get(x2-1)-eps);

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

                    for(int j=yy; j<=y2; j++) {

                        if(vv[i][j] <= eps)	continue;

                        if(ok(i, j))

                            ans++;

                    }

                }

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

            } else {

            	int yy = floor(get(x1+1)-eps);

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

                    for(int j=yy; j<=y1; j++) {

                        if(vv[i][j] <= eps)	continue;

                        if(ok(i, j))

                            ans++;

                    }

                }

                for(int x=x1+1; x<x2; x++) {

                    int yl = ceil(get(x-1)+eps);

                    int yr = floor(get(x+1)-eps);

                    for(int i=x; i<=x; i++) {

                        for(int j=yr; j<=yl; j++) {

                            if(vv[i][j] <= eps)	continue;

                            if(ok(i, j))

                                ans++;

                        }

                    }

                }

                yy = ceil(get(x2-1)+eps);

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

                    for(int j=y2; j<=yy; j++) {

                        if(vv[i][j] <= eps)	continue;

                        if(ok(i, j))

                            ans++;

                    }

                }

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

            }

        }

    }

    return 0;

}

巴特西

Ice Igloos Gym - 101480I (暴力技巧)

Problem I: Ice Igloos

题意

思路

最新文章

热门文章