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;}

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

相关推荐

GPT-5.6正式开放：Sol、Terra、Luna三档模型怎么选？开发者需要关注的7个变化

Spring AI项目找不到ChatClient Bean怎么解决？从自动配置到多模型冲突完整排查

DeepSeek旧模型名7月24日停止服务：deepseek-chat与deepseek-reasoner迁移清单

更多资讯

Python+Vue3跨平台学习行为分析系统开发实践

不用下载到本地：kkFileView 文件在线预览服务搭建指南

Roo Code 繁體中文（zh-TW）在地化翻譯指南：術語規範、格式規則與 i18n 實作解析

Anaconda环境管理：Python多版本与依赖隔离实战

MySQL 8.0客户端认证协议不兼容问题解决方案

A*算法优化：路径规划效率与质量的提升策略

今日更新

SpacetimeDB C++ 模块库实战：用 C++20 在数据库内构建 WebAssembly 模块

别踩雷！不是所有 AI 写作工具都靠谱，2026 高校认可工具精选

SSM+MySQL幼儿园管理系统源码解析：从部署到优化

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？