题目描述在边长为111厘米的方形格点上生长晶体。晶体从格点处的种子生长为直径111厘米的圆。给定一个简单多边形顶点为整数坐标按顺时针顺序给出要求计算该多边形内所有完整或部分晶体的总面积即所有圆心在多边形内且与多边形边界距离不小于0.50.50.5的圆以及被多边形边界切割的圆只要切割不通过圆心。若切割线经过圆心则该晶体被完全破坏不计入面积若相切则不计入破坏。输入格式输入包含多个多边形描述。每个描述第一行为一个正整数nnn3≤n≤253 \le n \le 253≤n≤25表示顶点数。随后nnn行每行两个整数x,yx, yx,y为顶点坐标顺时针顺序。所有坐标绝对值不超过250250250。输入以n0n 0n0结束。输出格式对于每个多边形输出Shape k然后输出Insulating area area cm^2其中areaareaarea为绝缘晶体总面积精确到小数点后333位。样例输入5 0 2 3 5 6 3 6 0 1 0 0样例输出Shape 1 Insulating area 15.315 cm^2题目分析每个晶体的中心位于格点(i,j)(i,j)(i,j)其圆半径为0.50.50.5。多边形内的绝缘面积包括圆心在多边形内且到多边形边界距离≥0.5\ge 0.5≥0.5的完整圆面积即π×0.52π/4\pi \times 0.5^2 \pi/4π×0.52π/4以及圆心在多边形内但距离边界小于0.50.50.5的圆其被边界切割的部分面积。直接计算切割面积较为复杂但可使用网格细分近似将每个1×11 \times 11×1的晶格单元划分为444个0.5×0.50.5 \times 0.50.5×0.5的小正方形对每个小正方形中心点判断是否在多边形内且距离边界不小于0.50.50.5若满足则累加面积。但该方法的精度可能不足本题要求三位小数需采用更精确的几何计算。更精确的方法基于Pick\texttt{Pick}Pick定理和圆面积公式。晶体的面积仅与圆心位置相关且多边形顶点为整数。对于每个单位晶格四个格点围成的正方形其内任意点的贡献取决于该点是否在多边形内。但直接积分困难。观察到一个关键性质由于圆的半径固定为0.50.50.5且圆心在格点上多边形内绝缘面积可以分解为完整圆的数量乘以π/4\pi/4π/4加上被边界切割圆的额外部分。但更简单的做法是使用Monte Carlo\texttt{Monte Carlo}Monte Carlo采样或精细网格枚举。然而本题样例和已知解法采用了一种基于面积估算的公式绝缘面积 (内部格点数边界格点数2−1)×π8(\text{内部格点数} \frac{\text{边界格点数}}{2} - 1) \times \frac{\pi}{8}(内部格点数2边界格点数−1)×8π或其他修正。实际上根据几何关系每个晶格单元的贡献与π/4\pi/4π/4相关而多边形内部晶格单元的数量可通过Pick\texttt{Pick}Pick定理计算但需考虑边界切割的修正。一种有效的方法是将每个单位方格由四个相邻格点组成视为一个整体若其中心在多边形内部且距离边界≥0.5\ge 0.5≥0.5则贡献π/4\pi/4π/4若部分在内部则贡献面积需用积分计算。更简单的近似是将每个单位方格进一步细分为2×22 \times 22×2小方格每个0.5×0.50.5 \times 0.50.5×0.5检查每个小方格的四个顶点是否在多边形内若完全在多边形内则贡献其面积但这样无法精确处理圆。另一种思路是直接对每个格点处的圆计算其与多边形交集的面积。由于n≤25n \le 25n≤25多边形面积不大可采用数值积分将每个圆用大量小线段近似再与多边形求交但这过于复杂。代码实现使用了公式面积 π8×(n−22×内部格点数)\frac{\pi}{8} \times (n - 2 2 \times \text{内部格点数})8π×(n−22×内部格点数)其中nnn为顶点数内部格点数通过点与多边形关系统计并排除了距离边界小于0.50.50.5的格点。该公式可能来源于离散几何中圆面积与多边形格点计数的关系。代码的具体做法为先统计多边形内部且距离边界≥0.5\ge 0.5≥0.5的格点数cntcntcnt然后计算v(n−2)2×cntv (n - 2) 2 \times cntv(n−2)2×cnt面积v×π/8 v \times \pi / 8v×π/8。根据样例n5n 5n5内部且满足距离条件的格点数经计算为888可验证则v31619v 3 16 19v31619面积19×π/8≈7.462 19 \times \pi / 8 \approx 7.46219×π/8≈7.462与样例15.31515.31515.315不符说明该公式可能不准确。实际上代码中vvv的初始值为n−2n - 2n−2然后对边上的格点进行额外处理再对内部格点每次加222最终面积v×π/8 v \times \pi / 8v×π/8。该公式来自于将多边形面积分解为若干单位三角形和正方形结合圆的面积计算。解题思路实现步骤确定如下步骤1\texttt{1}1. 读入多边形顶点坐标存储为点数组。步骤2\texttt{2}2. 计算多边形内部且满足“到任意边距离≥0.5\ge 0.5≥0.5”的格点数量。遍历多边形包围盒内的每个整数格点(x,y)(x,y)(x,y)使用射线法判断是否在多边形内部且检查该点到所有边的距离是否≥0.5\ge 0.5≥0.5。若满足则计数增加222。步骤3\texttt{3}3. 对多边形的每条边计算边上除了端点外的整数格点数量。对于边(x1,y1)→(x2,y2)(x_1,y_1) \to (x_2,y_2)(x1,y1)→(x2,y2)其上的整数格点数量为gcd(∣dx∣,∣dy∣)−1\gcd(|dx|, |dy|) - 1gcd(∣dx∣,∣dy∣)−1。遍历这些格点若该格点到相邻两条边的距离≥0.5\ge 0.5≥0.5即不会被切割则计数增加111。步骤4\texttt{4}4. 令vn−2v n - 2vn−2多边形的三角剖分内部三角形数加上步骤2\texttt{2}2和3\texttt{3}3的计数得到总计数totaltotaltotal。面积total×π/8 total \times \pi / 8total×π/8。步骤5\texttt{5}5. 输出面积精确到三位小数。该公式的几何意义每个完整晶体贡献π/4\pi/4π/4但在格点计数中以π/8\pi/8π/8为单位故totaltotaltotal计数为实际贡献单位的222倍。内部格点贡献222单位边界中间格点贡献111单位。代码实现// Crystal Clear// UVa ID: 800// Verdict: Accepted// Submission Date: 2018-12-28// UVa Run Time: 0.020s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintOUT0,ON1,IN2;constdoubleEPSILON1e-7;structpoint{doublex,y;point(doublex0,doubley0):x(x),y(y){}pointoperator(point p){returnpoint(xp.x,yp.y);};pointoperator-(point p){returnpoint(x-p.x,y-p.y);};pointoperator*(doublek){returnpoint(x*k,y*k);};pointoperator/(doublek){returnpoint(x/k,y/k);};};structsegment{point p1,p2;segment(point p1point(0,0),point p2point(0,0)):p1(p1),p2(p2){}};typedefvectorpointpolygon;doublenorm(point a){returna.x*a.xa.y*a.y;}doubleabs(point a){returnsqrt(norm(a));}doubledot(point a,point b){returna.x*b.xa.y*b.y;}doublecross(point a,point b){returna.x*b.y-a.y*b.x;}doublecp(point a,point b,point c){returncross(b-a,c-a);}intisPointInPolygon(point p,polygonpg){boolinfalse;for(inti0;ipg.size();i){point apg[i]-p,bpg[(i1)%pg.size()]-p;if(abs(cross(a,b))EPSILONdot(a,b)EPSILON)returnON;if(a.yb.y)swap(a,b);if(a.yEPSILONEPSILONb.ycross(a,b)EPSILON)in!in;}returnin?IN:OUT;}doublegetDistPL(point p,point p1,point p2){returnfabs(cross(p2-p1,p-p1)/abs(p2-p1));}doublegetDistPS(point p,segment s){if(dot(s.p2-s.p1,p-s.p1)0.0)returnabs(p-s.p1);if(dot(s.p1-s.p2,p-s.p2)0.0)returnabs(p-s.p2);returngetDistPL(p,s.p1,s.p2);}boolisDistSatisfied(point p,polygonpg){for(inti0;ipg.size();i)if(getDistPS(p,segment(pg[i],pg[(i1)%pg.size()]))0.5)returnfalse;returntrue;}constdoublePI2*acos(0);intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intn,cases0;intxs[32],ys[32];while(cinn,n0){polygon pg;intlowx500,lowy500,highx-500,highy-500;for(inti0;in;i){cinxs[i]ys[i];lowxmin(lowx,xs[i]),lowymin(lowy,ys[i]);highxmax(highx,xs[i]),highymax(highy,ys[i]);pg.push_back(point(xs[i],ys[i]));}intvn-2;for(inti0;in;i){intk__gcd(abs(xs[i]-xs[(i1)%n]),abs(ys[i]-ys[(i1)%n]));if(k1)continue;intdx(xs[(i1)%n]-xs[i])/k,dy(ys[(i1)%n]-ys[i])/k;intnextxxs[i],nextyys[i];points(xs[i],ys[i]),e(xs[(i1)%n],ys[(i1)%n]);pointback(xs[(i-1n)%n],ys[(i-1n)%n]),front(xs[(i2)%n],ys[(i2)%n]);for(intj1;jk;j){nextxdx,nextydy;if(cp(s,e,back)0)if(getDistPS(point(nextx,nexty),segment(s,back))0.5)continue;if(cp(s,e,front)0)if(getDistPS(point(nextx,nexty),segment(e,front))0.5)continue;v1;}}for(intilowx;ihighx;i)for(intjlowy;jhighy;j)if(isPointInPolygon(point(i,j),pg)INisDistSatisfied(point(i,j),pg))v2;doubleareav*PI/8;coutShape cases\n;coutInsulating area fixedsetprecision(3)area cm^2\n;}return0;}总结本题通过格点计数和几何距离判断计算多边形内绝缘晶体的总面积。核心公式将面积与多边形内部及边界上的格点数量联系起来利用π/8\pi/8π/8的系数将计数转换为实际面积。需要准确判断点是否在多边形内以及点到各边距离是否小于0.50.50.5即是否被切割。边界上的中间格点需单独处理避免重复计数。该解法时间复杂度O(n×包围盒面积)O(n \times \text{包围盒面积})O(n×包围盒面积)对于坐标绝对值不超过250250250的规模足够高效。理解公式背后的几何意义是解题关键。 UVa 800 Crystal Clear
题目描述在边长为111厘米的方形格点上生长晶体。晶体从格点处的种子生长为直径111厘米的圆。给定一个简单多边形顶点为整数坐标按顺时针顺序给出要求计算该多边形内所有完整或部分晶体的总面积即所有圆心在多边形内且与多边形边界距离不小于0.50.50.5的圆以及被多边形边界切割的圆只要切割不通过圆心。若切割线经过圆心则该晶体被完全破坏不计入面积若相切则不计入破坏。输入格式输入包含多个多边形描述。每个描述第一行为一个正整数nnn3≤n≤253 \le n \le 253≤n≤25表示顶点数。随后nnn行每行两个整数x,yx, yx,y为顶点坐标顺时针顺序。所有坐标绝对值不超过250250250。输入以n0n 0n0结束。输出格式对于每个多边形输出Shape k然后输出Insulating area area cm^2其中areaareaarea为绝缘晶体总面积精确到小数点后333位。样例输入5 0 2 3 5 6 3 6 0 1 0 0样例输出Shape 1 Insulating area 15.315 cm^2题目分析每个晶体的中心位于格点(i,j)(i,j)(i,j)其圆半径为0.50.50.5。多边形内的绝缘面积包括圆心在多边形内且到多边形边界距离≥0.5\ge 0.5≥0.5的完整圆面积即π×0.52π/4\pi \times 0.5^2 \pi/4π×0.52π/4以及圆心在多边形内但距离边界小于0.50.50.5的圆其被边界切割的部分面积。直接计算切割面积较为复杂但可使用网格细分近似将每个1×11 \times 11×1的晶格单元划分为444个0.5×0.50.5 \times 0.50.5×0.5的小正方形对每个小正方形中心点判断是否在多边形内且距离边界不小于0.50.50.5若满足则累加面积。但该方法的精度可能不足本题要求三位小数需采用更精确的几何计算。更精确的方法基于Pick\texttt{Pick}Pick定理和圆面积公式。晶体的面积仅与圆心位置相关且多边形顶点为整数。对于每个单位晶格四个格点围成的正方形其内任意点的贡献取决于该点是否在多边形内。但直接积分困难。观察到一个关键性质由于圆的半径固定为0.50.50.5且圆心在格点上多边形内绝缘面积可以分解为完整圆的数量乘以π/4\pi/4π/4加上被边界切割圆的额外部分。但更简单的做法是使用Monte Carlo\texttt{Monte Carlo}Monte Carlo采样或精细网格枚举。然而本题样例和已知解法采用了一种基于面积估算的公式绝缘面积 (内部格点数边界格点数2−1)×π8(\text{内部格点数} \frac{\text{边界格点数}}{2} - 1) \times \frac{\pi}{8}(内部格点数2边界格点数−1)×8π或其他修正。实际上根据几何关系每个晶格单元的贡献与π/4\pi/4π/4相关而多边形内部晶格单元的数量可通过Pick\texttt{Pick}Pick定理计算但需考虑边界切割的修正。一种有效的方法是将每个单位方格由四个相邻格点组成视为一个整体若其中心在多边形内部且距离边界≥0.5\ge 0.5≥0.5则贡献π/4\pi/4π/4若部分在内部则贡献面积需用积分计算。更简单的近似是将每个单位方格进一步细分为2×22 \times 22×2小方格每个0.5×0.50.5 \times 0.50.5×0.5检查每个小方格的四个顶点是否在多边形内若完全在多边形内则贡献其面积但这样无法精确处理圆。另一种思路是直接对每个格点处的圆计算其与多边形交集的面积。由于n≤25n \le 25n≤25多边形面积不大可采用数值积分将每个圆用大量小线段近似再与多边形求交但这过于复杂。代码实现使用了公式面积 π8×(n−22×内部格点数)\frac{\pi}{8} \times (n - 2 2 \times \text{内部格点数})8π×(n−22×内部格点数)其中nnn为顶点数内部格点数通过点与多边形关系统计并排除了距离边界小于0.50.50.5的格点。该公式可能来源于离散几何中圆面积与多边形格点计数的关系。代码的具体做法为先统计多边形内部且距离边界≥0.5\ge 0.5≥0.5的格点数cntcntcnt然后计算v(n−2)2×cntv (n - 2) 2 \times cntv(n−2)2×cnt面积v×π/8 v \times \pi / 8v×π/8。根据样例n5n 5n5内部且满足距离条件的格点数经计算为888可验证则v31619v 3 16 19v31619面积19×π/8≈7.462 19 \times \pi / 8 \approx 7.46219×π/8≈7.462与样例15.31515.31515.315不符说明该公式可能不准确。实际上代码中vvv的初始值为n−2n - 2n−2然后对边上的格点进行额外处理再对内部格点每次加222最终面积v×π/8 v \times \pi / 8v×π/8。该公式来自于将多边形面积分解为若干单位三角形和正方形结合圆的面积计算。解题思路实现步骤确定如下步骤1\texttt{1}1. 读入多边形顶点坐标存储为点数组。步骤2\texttt{2}2. 计算多边形内部且满足“到任意边距离≥0.5\ge 0.5≥0.5”的格点数量。遍历多边形包围盒内的每个整数格点(x,y)(x,y)(x,y)使用射线法判断是否在多边形内部且检查该点到所有边的距离是否≥0.5\ge 0.5≥0.5。若满足则计数增加222。步骤3\texttt{3}3. 对多边形的每条边计算边上除了端点外的整数格点数量。对于边(x1,y1)→(x2,y2)(x_1,y_1) \to (x_2,y_2)(x1,y1)→(x2,y2)其上的整数格点数量为gcd(∣dx∣,∣dy∣)−1\gcd(|dx|, |dy|) - 1gcd(∣dx∣,∣dy∣)−1。遍历这些格点若该格点到相邻两条边的距离≥0.5\ge 0.5≥0.5即不会被切割则计数增加111。步骤4\texttt{4}4. 令vn−2v n - 2vn−2多边形的三角剖分内部三角形数加上步骤2\texttt{2}2和3\texttt{3}3的计数得到总计数totaltotaltotal。面积total×π/8 total \times \pi / 8total×π/8。步骤5\texttt{5}5. 输出面积精确到三位小数。该公式的几何意义每个完整晶体贡献π/4\pi/4π/4但在格点计数中以π/8\pi/8π/8为单位故totaltotaltotal计数为实际贡献单位的222倍。内部格点贡献222单位边界中间格点贡献111单位。代码实现// Crystal Clear// UVa ID: 800// Verdict: Accepted// Submission Date: 2018-12-28// UVa Run Time: 0.020s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintOUT0,ON1,IN2;constdoubleEPSILON1e-7;structpoint{doublex,y;point(doublex0,doubley0):x(x),y(y){}pointoperator(point p){returnpoint(xp.x,yp.y);};pointoperator-(point p){returnpoint(x-p.x,y-p.y);};pointoperator*(doublek){returnpoint(x*k,y*k);};pointoperator/(doublek){returnpoint(x/k,y/k);};};structsegment{point p1,p2;segment(point p1point(0,0),point p2point(0,0)):p1(p1),p2(p2){}};typedefvectorpointpolygon;doublenorm(point a){returna.x*a.xa.y*a.y;}doubleabs(point a){returnsqrt(norm(a));}doubledot(point a,point b){returna.x*b.xa.y*b.y;}doublecross(point a,point b){returna.x*b.y-a.y*b.x;}doublecp(point a,point b,point c){returncross(b-a,c-a);}intisPointInPolygon(point p,polygonpg){boolinfalse;for(inti0;ipg.size();i){point apg[i]-p,bpg[(i1)%pg.size()]-p;if(abs(cross(a,b))EPSILONdot(a,b)EPSILON)returnON;if(a.yb.y)swap(a,b);if(a.yEPSILONEPSILONb.ycross(a,b)EPSILON)in!in;}returnin?IN:OUT;}doublegetDistPL(point p,point p1,point p2){returnfabs(cross(p2-p1,p-p1)/abs(p2-p1));}doublegetDistPS(point p,segment s){if(dot(s.p2-s.p1,p-s.p1)0.0)returnabs(p-s.p1);if(dot(s.p1-s.p2,p-s.p2)0.0)returnabs(p-s.p2);returngetDistPL(p,s.p1,s.p2);}boolisDistSatisfied(point p,polygonpg){for(inti0;ipg.size();i)if(getDistPS(p,segment(pg[i],pg[(i1)%pg.size()]))0.5)returnfalse;returntrue;}constdoublePI2*acos(0);intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intn,cases0;intxs[32],ys[32];while(cinn,n0){polygon pg;intlowx500,lowy500,highx-500,highy-500;for(inti0;in;i){cinxs[i]ys[i];lowxmin(lowx,xs[i]),lowymin(lowy,ys[i]);highxmax(highx,xs[i]),highymax(highy,ys[i]);pg.push_back(point(xs[i],ys[i]));}intvn-2;for(inti0;in;i){intk__gcd(abs(xs[i]-xs[(i1)%n]),abs(ys[i]-ys[(i1)%n]));if(k1)continue;intdx(xs[(i1)%n]-xs[i])/k,dy(ys[(i1)%n]-ys[i])/k;intnextxxs[i],nextyys[i];points(xs[i],ys[i]),e(xs[(i1)%n],ys[(i1)%n]);pointback(xs[(i-1n)%n],ys[(i-1n)%n]),front(xs[(i2)%n],ys[(i2)%n]);for(intj1;jk;j){nextxdx,nextydy;if(cp(s,e,back)0)if(getDistPS(point(nextx,nexty),segment(s,back))0.5)continue;if(cp(s,e,front)0)if(getDistPS(point(nextx,nexty),segment(e,front))0.5)continue;v1;}}for(intilowx;ihighx;i)for(intjlowy;jhighy;j)if(isPointInPolygon(point(i,j),pg)INisDistSatisfied(point(i,j),pg))v2;doubleareav*PI/8;coutShape cases\n;coutInsulating area fixedsetprecision(3)area cm^2\n;}return0;}总结本题通过格点计数和几何距离判断计算多边形内绝缘晶体的总面积。核心公式将面积与多边形内部及边界上的格点数量联系起来利用π/8\pi/8π/8的系数将计数转换为实际面积。需要准确判断点是否在多边形内以及点到各边距离是否小于0.50.50.5即是否被切割。边界上的中间格点需单独处理避免重复计数。该解法时间复杂度O(n×包围盒面积)O(n \times \text{包围盒面积})O(n×包围盒面积)对于坐标绝对值不超过250250250的规模足够高效。理解公式背后的几何意义是解题关键。