UVa 688 Mobile Phone Coverage

题目描述给定若干个天线每个天线有一个位置(xi,yi)(x_i, y_i)(xi​,yi​)和半径rir_iri​。覆盖区域定义为以(xi,yi)(x_i, y_i)(xi​,yi​)为中心、边长为2ri2r_i2ri​的轴对齐正方形即L∞L_\inftyL∞​范数下的圆。求所有天线覆盖区域的并集面积n≤100n \le 100n≤100坐标和半径均为000到200200200的浮点数。输入格式多组数据每组第一行为整数nnn若n0n0n0结束。接下来nnn行每行三个浮点数xix_ixi​、yiy_iyi​、rir_iri​。输出格式对于每组数据输出一行格式为case_number area面积保留两位小数。样例输入3 4.0 4.0 3.0 5.0 6.0 3.0 5.5 4.5 1.0 2 3.0 3.0 3.0 1.5 1.5 1.0 0输出1 52.00 2 36.00题目分析本题要求多个轴对齐正方形的并集面积。由于n≤100n \le 100n≤100坐标范围有限可以使用扫描线 离散化的经典方法将所有正方形的左右边界xxx坐标和上下边界yyy坐标分别收集、排序、去重形成网格。然后遍历每个网格单元检查该单元是否被至少一个正方形覆盖若被覆盖则累加面积。由于坐标是浮点数直接离散化所有边界坐标网格数最多(2n)240000(2n)^2 40000(2n)240000每个网格检查nnn个正方形总复杂度O(n3)O(n^3)O(n3)但n100n100n100时约为10610^6106完全可接受。解题思路读入nnn个正方形记录其左右边界x[i] - r[i]和x[i] r[i]上下边界y[i] - r[i]和y[i] r[i]。将所有左右边界放入数组dx上下边界放入dy分别排序。遍历相邻的dx区间[dx[i-1], dx[i]]和dy区间[dy[j-1], dy[j]]检查是否存在一个正方形kkk使得该区间完全落在其内部即dx[i-1] x[k]-r[k]且dx[i] x[k]r[k]且dy[j-1] y[k]-r[k]且dy[j] y[k]r[k]。若存在则累加面积(dx[i] - dx[i-1]) * (dy[j] - dy[j-1])。输出结果。复杂度分析离散化O(nlog⁡n)O(n \log n)O(nlogn)。网格遍历O((2n)2⋅n)O(n3)O((2n)^2 \cdot n) O(n^3)O((2n)2⋅n)O(n3)n≤100n \le 100n≤100约4×1064 \times 10^64×106次检查可行。代码实现// Mobile Phone Coverage// UVa ID: 688// Verdict: Accepted// Submission Date: 2017-06-06// UVa Run Time: 0.010s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intn;doublearea,x[105],y[105],r[105],dx[105*2],dy[105*2];intcases0;while(cinnn){for(inti0;in;i){cinx[i]y[i]r[i];dx[i*2]x[i]-r[i],dx[i*21]x[i]r[i];dy[i*2]y[i]-r[i],dy[i*21]y[i]r[i];}sort(dx,dx2*n);sort(dy,dy2*n);doublearea0.0;for(inti1;i2*n;i)for(intj1;j2*n;j)for(intk0;kn;k){if(dx[i-1]x[k]-r[k]dx[i]x[k]r[k])if(dy[j-1]y[k]-r[k]dy[j]y[k]r[k]){area(dx[i]-dx[i-1])*(dy[j]-dy[j-1]);break;}}coutcases fixedsetprecision(2)area\n;}return0;}总结本题通过离散化边界坐标将连续面积问题转化为离散网格的覆盖判断简化了计算。关键点包括正确收集所有正方形的边界坐标。利用浮点数比较判断网格单元是否被覆盖。累加面积时注意精度。该解法是计算几何中“矩形并集面积”的经典离散化方法适用于nnn较小的情况。