Forsaken喜欢正方形【牛客tracker 每日一题】

Forsaken喜欢正方形时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述​F o r s a k e n ForsakenForsaken特别喜欢正方形现在他有二维平面的四个整点。如果四个整点可以直接形成一个正方形输出 w e n wenwen。如果可以通过对其中一个点进行一次轻微的调整使得四个整点形成一个正方形输出“ h a i x i n g ” “hai xing”“haixing”轻微的调整是指如果当前整点坐标为( x , y ) (x,y)(x,y)那么我们可以把这个点变成( x 1 , y ) , ( x − 1 , y ) , ( x , y 1 ) , ( x , y − 1 ) (x1,y),(x−1,y),(x,y1),(x,y−1)(x1,y),(x−1,y),(x,y1),(x,y−1)中的一种。否则如果都不行输出“ w o j u e d e b u x i n g ” “wo jue de bu xing”“wojuedebuxing”。输入描述输入有四行每行一个二维坐标( x , y ) (x,y)(x,y)输出描述按题面给定输出。示例1输入0 0 0 1 1 1 1 0输出wen备注0 ≤ x , y ≤ 100 0≤x,y≤1000≤x,y≤100解题思路本题是几何判定 小规模枚举的模拟题通过距离平法规避浮点误差判定正方形再枚举所有单点微调方案按优先级分级输出对应结果。1. 正方形判定距离平方法为避免开根号带来的浮点精度问题所有距离均使用平方值计算。代码采用简化判定逻辑以第一个点为基准计算它到另外三个点的距离平方排序后满足两个条件则判定为正方形两个较短的距离平方相等对应两条邻边长度相同最长的距离平方等于较短距离的2倍对应对角线平方 2 × 边长平方符合勾股定理的直角特性严谨补充更完备的正方形判定需要计算全部6组两两距离平方排序后前4个为等长边长、后2个为等长对角线且对角线平方为边长平方的2倍同时边长不为0可覆盖特殊点分布的误判场景。2. 三级判定流程按题目要求的优先级依次判断原图判定直接对输入的四个点执行正方形校验若成立直接输出wen。单点调整枚举原图不满足时枚举所有合法的单点调整方案共4个点每个点可向上下左右四个方向各移动1格总计 4×416 种调整方案。对每种方案临时修改对应点坐标调用判定函数验证只要存在一种方案能构成正方形即可输出hai xing。无解判定所有调整方案均不满足时输出wo jue de bu xing。3. 复杂度分析所有判定和枚举均为常数级运算总计算量极小远低于时间限制。总结核心逻辑基于距离平方的正方形判定先校验原图是否为正方形再枚举16种单点偏移方案逐一验证按优先级输出对应结果。关键操作距离平方规避浮点误差、四方向偏移枚举、修改后坐标回溯、分级提前终止优化。效率保障总枚举量仅16次判定常数级开销运行速度极快。代码简要说明距离计算函数cul接收两个点坐标计算两点间距离的平方并返回使用pow计算坐标差的平方后求和采用long long类型避免数值溢出。正方形判定函数check计算第一个点到其余三个点的距离平方存入向量后从小到大排序。判断前两个短距离相等且最长距离为短距离的2倍满足条件则返回true。主逻辑solve函数读入四个点坐标存入pt向量先校验原图若为正方形直接输出wen并返回。定义上下左右四个方向的偏移量数组dx、dy。双层循环枚举每个点和每个偏移方向临时修改点坐标后判定若满足条件则标记flag1随后立即恢复点的原坐标回溯找到可行解后提前跳出循环。根据flag输出对应结果存在可行调整方案输出hai xing否则输出wo jue de bu xing。输入优化关闭流同步并解绑tie提升输入输出的运行效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;llcul(pll p1,pll p2){return((ll)pow(p1.second-p2.second,2))((ll)pow(p1.first-p2.first,2));}boolcheck(vectorpllpt){vectorlllen;for(ll i1;i4;i)len.push_back(cul(pt[0],pt[i]));sort(len.begin(),len.end());if(len[0]len[1]len[2]len[0]*2)returntrue;returnfalse;}voidsolve(){vectorpllpt;for(ll i0;i4;i){ll x,y;cinxy;pt.push_back({x,y});}if(check(pt))coutwen\n;else{ll dx[]{0,0,1,-1};ll dy[]{1,-1,0,0};ll flag0;for(ll i0;i4;i){for(ll j0;j4;j){pt[i].firstdx[j];pt[i].seconddy[j];if(check(pt))flag1;pt[i].first-dx[j];pt[i].second-dy[j];if(flag)break;}if(flag)break;}cout(flag?hai xing:wo jue de bu xing)\n;}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);solve();return0;}