打卡信奥刷题（3227）用C++实现信奥题 P8404 [CCC 2022 J5] Square Pool

P8404 [CCC 2022 J5] Square Pool题目描述罗恩想在他的n×nn\times nn×n的正方形院子里建一个正方形游泳池但他的院子里有TTT棵树。你的任务是确定他可以建造的最大的方形游泳池的边长。输入格式第一行一个整数nnn具体意义见题目描述。第二行一个整数TTT具体意义见题目描述。接下来TTT行每行两个整数x,yx,yx,y表示在(x,y)(x,y)(x,y)上有一棵树。输出格式一行表示游泳池的最大边长。输入输出样例 #1输入 #15 1 2 4输出 #13输入输出样例 #2输入 #215 8 4 7 4 1 14 11 10 6 13 4 4 10 10 3 9 14输出 #27说明/提示样例111解释样例222解释对于20%20\%20%的数据1≤n≤50,T11\le n\le 50,T11≤n≤50,T1对于35%35\%35%的数据1≤n≤50,1≤T≤101\le n\le 50,1\le T\le 101≤n≤50,1≤T≤10对于25%25\%25%的数据1≤n≤5×105,1≤T≤101\le n\le 5\times 10^5,1\le T\le 101≤n≤5×105,1≤T≤10对于100%100\%100%的数据1≤n≤5×105,1≤T≤1001\le n\le 5\times 10^5,1\le T\le 1001≤n≤5×105,1≤T≤100C实现#includebits/stdc.husingnamespacestd;constintMAXT105;intn,t;structnode{intx,y;}tree[MAXT];boolcmp1(node a,node b){returna.xb.x;}boolcmp2(node a,node b){returna.yb.y;}intmain(){scanf(%d%d,n,t);n;for(inti1;it;i)scanf(%d%d,tree[i].x,tree[i].y);tree[t]{0,0},tree[t]{0,n};tree[t]{n,n},tree[t]{n,0};sort(tree1,tree1t,cmp1);intans0;for(inti1;it;i){intminn1,maxnn;for(intji1;jt;j){if(maxn-minn-1tree[j].x-tree[i].x-1)break;ansmax(ans,tree[j].x-tree[i].x-1);if(tree[j].ytree[i].y)minnmax(minn,tree[j].y);if(tree[j].ytree[i].y)maxnmin(maxn,tree[j].y);}}sort(tree1,tree1t,cmp2);for(inti1;it;i){intminn1,maxnn;for(intji1;jt;j){if(maxn-minn-1tree[j].y-tree[i].y-1)break;ansmax(ans,tree[j].y-tree[i].y-1);if(tree[j].xtree[i].x)minnmax(minn,tree[j].x);if(tree[j].xtree[i].x)maxnmin(maxn,tree[j].x);}}coutans;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容