题目描述在一个2049 × 2049 2049 \times 20492049×2049的网格上坐标范围从( 0 , 0 ) (0,0)(0,0)到( 2048 , 2048 ) (2048,2048)(2048,2048)我们需要根据给定的规则绘制一系列嵌套的正方形并计算一个给定点被多少个正方形所包围包括边界。正方形的定义规则如下最大的正方形大小为k kk即边长为2 k 1 2k12k1中心位于网格中心( 1024 , 1024 ) (1024,1024)(1024,1024)。允许的正方形大小范围1 ≤ k ≤ 512 1 \leq k \leq 5121≤k≤512。对于大小k 1 k 1k1的正方形需要在它的四个角上分别放置一个大小为⌊ k / 2 ⌋ \lfloor k/2 \rfloor⌊k/2⌋的正方形。如果一个点位于正方形的边界上也算作被该正方形包围。给定k kk值和点的坐标( x , y ) (x,y)(x,y)需要计算有多少个正方形包含该点。题目分析与解题思路问题本质理解这是一个递归生成图形并统计点包含关系的问题。从最大的中心正方形开始按照规则不断在四个角上生成更小的正方形直到正方形大小变为1 11为止。整个过程形成了一种四叉树的结构。关键点分析坐标系的设定左上角为( 0 , 0 ) (0,0)(0,0)右下角为( 2048 , 2048 ) (2048,2048)(2048,2048)。中心点坐标固定为( 1024 , 1024 ) (1024,1024)(1024,1024)。正方形的表示大小为k kk的正方形边长实际为2 k 1 2k12k1。给定中心点( c x , c y ) (cx,cy)(cx,cy)和大小k kk正方形的范围是左边界c x − k cx - kcx−k右边界c x k cx kcxk上边界c y − k cy - kcy−k下边界c y k cy kcyk包含关系的判断点( x , y ) (x,y)(x,y)被正方形包含的条件是c x − k ≤ x ≤ c x k 且 c y − k ≤ y ≤ c y k cx - k \leq x \leq cx k \quad \text{且} \quad cy - k \leq y \leq cy kcx−k≤x≤cxk且cy−k≤y≤cyk注意边界上的点也算被包含因此使用≤ \leq≤而非 。递归生成规则对于大小k 1 k 1k1的正方形在四个角上生成大小为⌊ k / 2 ⌋ \lfloor k/2 \rfloor⌊k/2⌋的正方形。四个角的位置分别是左上角( c x − k , c y − k ) (cx - k, cy - k)(cx−k,cy−k)右上角( c x k , c y − k ) (cx k, cy - k)(cxk,cy−k)右下角( c x k , c y k ) (cx k, cy k)(cxk,cyk)左下角( c x − k , c y k ) (cx - k, cy k)(cx−k,cyk)注意这里使用的是当前正方形的边界坐标作为新正方形的中心点。算法设计这是一个典型的深度优先搜索问题从最大的中心正方形开始判断当前正方形是否包含目标点。如果包含计数器加1 11。如果当前正方形大小k 1 k 1k1则递归处理四个角上的子正方形。递归结束条件正方形大小变为1 11此时k 1 k1k1无法再生成更小的正方形。复杂度分析每个正方形会生成4 44个子正方形形成一棵四叉树。树的高度为log 2 k \log_2 klog2k总节点数约为4 log 2 k k 2 4^{\log_2 k} k^24log2kk2。对于最大k 512 k512k512节点数约为512 2 262144 512^2 2621445122262144完全可行。每个节点只进行常数次判断操作因此总时间复杂度为O ( k 2 ) O(k^2)O(k2)。实现细节使用全局变量记录目标点坐标和计数器。递归函数参数当前正方形的大小k kk和中心点坐标( c x , c y ) (cx,cy)(cx,cy)。注意k kk的更新k k / 2 k k / 2kk/2整数除法。代码实现// All Squares// UVa ID: 155// Verdict: Accepted// Submission Date: 2016-02-03// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net//// 题目描述似乎有问题。#includebits/stdc.husingnamespacestd;intx,y;intcounter;boolpointInSquare(intcenterx,intcentery,intsize){return(centerx-sizex)(xcenterxsize)(centery-sizey)(ycenterysize);}voidgenerateSquare(intk,intcenterx,intcentery){intsidek;if(pointInSquare(centerx,centery,side))counter;if(k1){k/2;generateSquare(k,centerx-side,centery-side);generateSquare(k,centerxside,centery-side);generateSquare(k,centerxside,centeryside);generateSquare(k,centerx-side,centeryside);}}intmain(){intk;while(cinkxy,k||x||y){counter0;generateSquare(k,1024,1024);coutsetw(3)rightcounterendl;}return0;}示例验证输入500 113 941 0 0 0输出5输出格式要求右对齐宽度为3 33因此5 55显示为5。总结本题通过递归方式构建嵌套正方形并在构建过程中统计点被包含的次数。理解正方形的定义和递归生成规则是关键。代码实现简洁高效利用全局变量和递归函数很好地解决了问题。需要注意的地方边界上的点也算被包含判断条件要用≤ \leq≤。递归时使用当前正方形的边界坐标作为子正方形的中心点。输出格式要求右对齐宽度3 33需要使用setw(3) \texttt{setw(3)}setw(3)控制格式。