企业官网建设流程全解析

Forsaken喜欢正方形

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

​F o r s a k e n ForsakenForsaken特别喜欢正方形，现在他有二维平面的四个整点。如果四个整点可以直接形成一个正方形，输出" w e n " "wen""wen"。如果可以通过对其中一个点进行一次轻微的调整使得四个整点形成一个正方形，输出“ 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 ) (x+1,y),(x−1,y),(x,y+1),(x,y−1)(x+1,y),(x−1,y),(x,y+1),(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. 三级判定流程

按题目要求的优先级依次判断：

1. 原图判定：直接对输入的四个点执行正方形校验，若成立直接输出"wen"。
2. 单点调整枚举：原图不满足时，枚举所有合法的单点调整方案：
   • 共4个点，每个点可向上下左右四个方向各移动1格，总计 4×4=16 种调整方案。
   • 对每种方案临时修改对应点坐标，调用判定函数验证，只要存在一种方案能构成正方形，即可输出"hai xing"。
3. 无解判定：所有调整方案均不满足时，输出"wo jue de bu xing"。

3. 复杂度分析

所有判定和枚举均为常数级运算，总计算量极小，远低于时间限制。

总结

核心逻辑：基于距离平方的正方形判定，先校验原图是否为正方形，再枚举16种单点偏移方案逐一验证，按优先级输出对应结果。
关键操作：距离平方规避浮点误差、四方向偏移枚举、修改后坐标回溯、分级提前终止优化。
效率保障：总枚举量仅16次判定，常数级开销，运行速度极快。

代码简要说明

1. 距离计算函数cul：接收两个点坐标，计算两点间距离的平方并返回，使用pow计算坐标差的平方后求和，采用long long类型避免数值溢出。
2. 正方形判定函数check：
   • 计算第一个点到其余三个点的距离平方，存入向量后从小到大排序。
   • 判断前两个短距离相等，且最长距离为短距离的2倍，满足条件则返回true。
3. 主逻辑solve函数：
   • 读入四个点坐标存入pt向量，先校验原图，若为正方形直接输出wen并返回。
   • 定义上下左右四个方向的偏移量数组dx、dy。
   • 双层循环枚举每个点和每个偏移方向：临时修改点坐标后判定，若满足条件则标记flag=1，随后立即恢复点的原坐标（回溯），找到可行解后提前跳出循环。
   • 根据flag输出对应结果：存在可行调整方案输出hai xing，否则输出wo jue de bu xing。
4. 输入优化：关闭流同步并解绑tie，提升输入输出的运行效率。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;llcul(pll p1,pll p2){return((ll)pow(p1.second-p2.second,2))+((ll)pow(p1.first-p2.first,2));}boolcheck(vector<pll>&pt){vector<ll>len;for(ll i=1;i<4;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(){vector<pll>pt;for(ll i=0;i<4;i++){ll x,y;cin>>x>>y;pt.push_back({x,y});}if(check(pt))cout<<"wen"<<'\n';else{ll dx[]={0,0,1,-1};ll dy[]={1,-1,0,0};ll flag=0;for(ll i=0;i<4;i++){for(ll j=0;j<4;j++){pt[i].first+=dx[j];pt[i].second+=dy[j];if(check(pt))flag=1;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;}