欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年青铜组真题解析 | 汇总-CSDN博客
【题目来源】
洛谷：[P1696 USACO18JAN] Blocked Billboard II B - 洛谷 (luogu.com.cn)
【题目描述】
奶牛Bassie想要覆盖一大块广告牌，她在之前已经覆盖了一小部分广告牌（但覆盖的这块面积不一定在广告牌上）
现在她要取一块足够大的布来将剩下的部分覆盖，问至少要多大的矩形的布才能覆盖剩下的广告牌。
【输入】
输入共两行。
第一行四个整数，l 1 l_1l1,****r 1 r_1r1,****l 2 l_2l2,****r 2 r_2r2，描述广告牌左下和右上两个坐标**( l 1 , r 1 ) (l_1,r_1)(l1,r1)和( l 2 , r 2 ) (l_2,r_2)(l2,r2)**。
第二行四个整数，x 1 , y 1 , x 2 , y 2 x_1,y_1,x_2,y_2x1,y1,x2,y2，描述覆盖的位置的左下和右上两个坐标**( x 1 , y 1 ) (x_1,y_1)(x1,y1)和( x 2 , y 2 ) (x_2,y_2)(x2,y2)**。
所有数值都在**− 1000 ∼ 1000 -1000\sim 1000−1000∼1000**范围内。
【输出】
一行一个整数，表示需要的最小的矩形的布。
【输入样例】
2 1 7 4 5 -1 10 3【输出样例】
15【算法标签】
《洛谷 P1696 Blocked Billboard II》 #USACO# #O2优化# #2018#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;inta[5],b[5];// 存储两个矩形的坐标：a[广告牌], b[覆盖物]intans=0,ans2=0;// ans: 未被覆盖的面积, ans2: 被覆盖的面积intx[5],y[5];// 存储所有x坐标和y坐标（用于网格划分）// 矩形的四个顶点坐标intx11,x12,x21,x22;// 广告牌和覆盖物的x坐标inty11,y12,y21,y22;// 广告牌和覆盖物的y坐标ifstreamfilein("billboard.in");ofstreamfileout("billboard.out");/** * 判断网格单元是否在矩形内部 * @param i x方向网格索引 * @param j y方向网格索引 * @param k 矩形的坐标数组 * @return 如果网格单元完全在矩形内返回true，否则false */boolin(inti,intj,intk[]){// 检查网格单元是否完全包含在矩形内if(x[i]>=k[1]&&x[i+1]<=k[3]&&y[j]>=k[2]&&y[j+1]<=k[4]){returntrue;}returnfalse;}intmain(){// 输入广告牌的坐标（左下角和右上角）for(inti=1;i<=4;i++){filein>>a[i];}x11=a[1];// 广告牌左下角xx12=a[3];// 广告牌右上角xy11=a[2];// 广告牌左下角yy12=a[4];// 广告牌右上角y// 输入覆盖物的坐标（左下角和右上角）for(inti=1;i<=4;i++){filein>>b[i];}x21=b[1];// 覆盖物左下角xx22=b[3];// 覆盖物右上角xy21=b[2];// 覆盖物左下角yy22=b[4];// 覆盖物右上角y// 收集所有x坐标和y坐标x[1]=a[1];// 广告牌左边界x[2]=a[3];// 广告牌右边界x[3]=b[1];// 覆盖物左边界x[4]=b[3];// 覆盖物右边界y[1]=a[2];// 广告牌下边界y[2]=a[4];// 广告牌上边界y[3]=b[2];// 覆盖物下边界y[4]=b[4];// 覆盖物上边界// 对坐标进行排序，用于网格划分sort(x+1,x+4+1);sort(y+1,y+4+1);// 特殊情况处理：覆盖物完全包含广告牌或广告牌完全包含覆盖物if((y22>=y12&&y11>=y21&&x12>=x22&&x21>=x11)||(y12>=y22&&y21>=y11&&x22>=x12&&x11>=x21)){// 输出广告牌的面积（完全被覆盖或完全覆盖）fileout<<(y12-y11)*(x12-x11)<<endl;return0;}// 遍历所有网格单元（3x3网格）for(inti=1;i<=3;i++){for(intj=1;j<=3;j++){// 检查网格单元是否在广告牌内但不在覆盖物内if(in(i,j,a)&&!in(i,j,b)){// 计算未被覆盖的网格单元面积并累加ans+=(y[j+1]-y[j])*(x[i+1]-x[i]);}// 检查网格单元是否同时在广告牌和覆盖物内if(in(i,j,a)&&in(i,j,b)){// 计算被覆盖的网格单元面积并累加ans2+=(y[j+1]-y[j])*(x[i+1]-x[i]);}}}// 特殊情况：部分覆盖且覆盖区域不规则if(ans2%(y12-y11)!=0&&ans2%(x12-x11)!=0){// 使用整个广告牌的面积作为结果ans=(y12-y11)*(x12-x11);}// 输出未被覆盖的面积fileout<<ans<<endl;return0;}【运行结果】
2 1 7 4 5 -1 10 3 15
