题解 P4354 【[CERC2015]Ice Igloos】

· · 题解

一道经典的计算几何题，并不难然而我还是交了好多遍

我们有两个思路：

一.暴力：对于每一条给出的线段，我们把每一个圆扫一遍并判断是否相交，但是这样太慢了，最后四个点TLE跑不掉惹QAQ。。。

方法还是值得借鉴的：

1) 如果线段有且只有一个端点在圆内，肯定相交

2) 如果线段两个端点都在圆内，肯定不相交

3) 如果线段两个端点都不在圆内，则可以用距离公式去判断是否相交

想要图？没有图，自己脑补

代码如下：

 #include<cstdio>
#include<cmath>
#include<algorithm>
#define _ 0
#define N 200000
#define drep(k ,l ,r) for(register int k = (l) ; k >= r ; -- k)
#define rep(k ,l ,r) for(register int k = l ; k <= r ; ++ k)
#define re register
using namespace std;
struct node {
    int x ,y;
    double r;
} cir[N];
int n ,m ,_x1 ,_yi ,_x2 ,_y2;
int read() {
    char cc = getchar() ; int cn = 0 ,flus = 1;
    while(cc < '0' || cc > '9') {if(cc == '-') flus = - flus ; cc = getchar();}
    while(cc >= '0' && cc <= '9') cn = cn * 10 + cc - '0' ,cc = getchar();
    return flus * cn;
}
bool in_cir(int _x ,int _y ,int now) {//判断点是否在圆内
    if((_x - cir[now].x) * (_x - cir[now].x) + (_y - cir[now].y) * (_y - cir[now].y) - cir[now].r * cir[now].r <= 0) 
        return 1;
    return 0;
}
bool judge(int now) {//总的判断函数
    re bool inc1 = in_cir(_x1 ,_yi ,now) ,inc2 = in_cir(_x2 ,_y2 ,now);
    if(inc1 && inc2) return 0;
    if(((!inc1) && inc2) || ((!inc2) && inc1)) return 1;
    re double A ,B ,C ,dis1 ,dis2 ,ang1 ,ang2;
    if(_x1 == _x2) A = 1 ,B = 0 ,C = - _x1;
    else if(_yi == _y2) A = 0 ,B = 1 ,C = - _yi;
         else A = _yi - _y2 ,B = _x2 - _x1 ,C = _x1 * _y2 - _x2 * _yi;
    /*dis1 = A * cir[now].x + B * cir[now].y + C; dis1 *= dis1;
    dis2 = (A * A + B * B) * cir[now].r * cir[now].r;
    if(dis1 > dis2) return 0;
    ang1 = (cir[now].x - _x1) * (_x2 - _x1) + (cir[now].y - _yi) * (_y2 - _yi);
    ang2 = (cir[now].x - _x2) * (_x1 - _x2) + (cir[now].y - _y2) * (_yi - _y2);
    if(ang1 > 0 && ang2 > 0) return 1;
    return 0;*/ 利用余弦公柿判断是否相交，然而还比距离公柿麻烦多了
    double d = abs((A * cir[now].x + B * cir[now].y + C) / sqrt(A * A + B * B));//距离公柿
    return cir[now].r - d >= 0;
}
int main() {
    n = read();
    rep(i ,1 ,n) cir[i].x = read() ,cir[i].y = read() ,scanf("%lf" ,&cir[i].r);
    m = read();
    while(m --) {
        re int ans = 0;
        _x1 = read() ,_yi = read() ,_x2 = read() ,_y2 = read();
        rep(i ,1 ,n) {
            if((max(_yi ,_y2) >= cir[i].y - cir[i].r) && min(_yi ,_y2) <= cir[i].y + cir[i].r && max(_x1 ,_x2) >= cir[i].x - cir[i].r && min(_x1 ,_x2) <= cir[i].x + cir[i].r)//一个并无啥子用的特判
            if(judge(i)) ++ans;
        }
        printf("%d\n" ,ans);
    }
    return ~~(0^_^0);
}

然后你就有了63分，并为怎么剪枝而抓狂。。。。。。

最后这种方法还是被我抛弃了QAQ

二.暴力：对于每一条给出的线段，枚举线段上的每一个整数 x 和每一个对应的 y ,因为圆的半径 r\leq1,所以我们只需要在一定范围内查找是否有圆，是否相交就行了。

1) 如果存在垂直于 x 轴的情况，那么只要判断线段经过的地方是否有圆。

2) 如果存在垂直于 y 轴的情况，同上。

3) 如果线段存在斜率，则需要划定一个区间去检查其中是否有圆。

代码如下：

#include<cstdio>
#include<algorithm>
#include<cmath>
#define _ 0
#define drep(k ,l ,r) for(register int k = (l) ; k >= (r) ; -- k)
#define rep(k ,l ,r) for(register int k = l ; k <= r ; ++ k)
#define re register 
using namespace std;
const int Eps = 1e-8;
double xoy[700][700] ,r ,k ,b ,len ,A ,B ,C;
int x1 ,yI ,x2 ,yS ,n ,m ,ans ,_x ,_y;
int read() {
    char cc = getchar() ; int cn = 0 ,flus = 1;
    while(cc < '0' || cc > '9') {if(cc == '-') flus = - flus ; cc = getchar();}
    while(cc >= '0' && cc <= '9') cn = cn * 10 + cc - '0' ,cc = getchar();
    return flus * cn;
}
void line() {//解直线
    A = (double)(yS - yI) ,B = (double)(x1 - x2) ,C = (double)yI * (double)(x2 - x1) + (double)x1 * (double)(yI - yS);
    re double tmp = (double)sqrt(A * A + B * B);
    A /= tmp ,B /= tmp ,C /= tmp;
    k = (double)(yS - yI) / (double)(x2 - x1) ,b = (double)(yI - x1 * k);
}
bool get(int x ,int y) {//判断是否相交
    re double tmp = fabs(A * x + B * y + C) - xoy[x][y];
    if(fabs(tmp) <= Eps || tmp <= 0) return 1;
    else return 0;
}
int maker(int op ,int y_ ,int y__) {//在区间内查询
    re int res = 0;
    rep(i ,y_ ,y__) {
        if(xoy[op][i] <= Eps) continue;
        res += get(op ,i);
    }
    return res;
}
int main() {
    n = read();
    while(n--) 
    x1 = read() ,yI = read() ,scanf("%lf" ,&r) ,xoy[x1][yI] = r;
    m = read();
    while(m --) {
        x1 = read() ,yI = read() ,x2 = read() ,yS = read() ,ans = 0;
        if(x1 == x2) {//垂直于x轴
            if(yI > yS) swap(yI ,yS);
            rep(i ,yI ,yS) if(xoy[x1][i]) ++ ans;//查询线段上是否存在圆，统计答案
        }
        else if(yI == yS) {//垂直于y轴
            if(x1 > x2) swap(x1 ,x2);
            rep(i ,x1 ,x2) if(xoy[i][yI]) ++ans;
        }
        else {
            if(x1 > x2 || ((x1 == x2) && (yI > yS))) swap(x1 ,x2) ,swap(yI ,yS);
            line();
            if(k > 0) {//递增
                ans += maker(x1 ,yI ,ceil(k * (x1 + 1) + b + Eps));//左端点
                rep(x ,x1 + 1 ,x2 - 1) ans += maker(x ,floor((double)(k * (x - 1) + b - Eps)) ,ceil((double)(k * (x + 1) + b + Eps)));//中间部分
                ans += maker(x2 ,floor(k * (x2 - 1) + b - Eps) ,yS);//右端点
            }
            else {//递减
                ans += maker(x1 ,floor(k * (x1 + 1) + b - Eps) ,yI);
                rep(x ,x1 + 1 ,x2 - 1) ans += maker(x ,floor((double)(k * (x + 1) + b - Eps)) ,ceil((double)(k * (x - 1) + b + Eps)));
                ans += maker(x2 ,yS ,ceil(k * (x2 - 1) + b + Eps));
            }
        }
        printf("%d\n" ,ans);
    }
    return ~~(0^_^0);
}

然后你就得到了100分QAQ

不怎么温馨的温馨提醒：因为头文件的锅 y1 不能直接定义,上面代码中的 _ yi 则为 y1 ,下面代码中的 yI 为 y1 , yS 为 y2别问，问就是心血来潮的全局替换