AcWing 1237. 螺旋折线
原题链接
中等
作者:
Ac-Wings
,
2021-04-16 22:31:22
,
所有人可见
,
阅读 2
这道题本质就是找规律,这次写题解的目的是为了帮助避雷
以下为超时代码
将距离分为两部分,一部分为该层内部所有正方形边长之和,另一部分为根据顺时针的特点,逆求该点到该正方形右下角的出发点的距离
#include<iostream>
#include<algorithm>
using namespace std;
int Dis(int d, int x, int y) {
int dis = 0;
if (x < 0 && d == abs(x))
dis = d + y;
if (y > 0 && d == y)
dis = 2 * d + x + d;
if (x > 0 && d == x)
dis = 4 * d + abs(y - d);
if (y < 0 && d == abs(y))
dis = 6 * d + abs(x - d);
return dis;
}
int main() {
int x, y;
cin >> x >> y;
int d = max(abs(x), abs(y));
int sum = 0;
for (int i = 0; i < d; i++) {
sum = sum + (2 * i) * 4;
}
int ans = sum + Dis(d, x, y);
cout << ans << endl;
return 0;
}
大佬代码,运行快,简洁。
主要将区域分为两块,每块再根据取值,具体进行细分上下区,最终分为四块,四块各自查找规律
#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
LL X,Y;
int main()
{
LL len=0;
cin>>X>>Y;
if(Y>=-X)
{
if(Y>X)
{
len=4*Y*Y;
len = len-abs(X-Y);
}
else
{
len=4*X*X;
len = len+abs(X-Y);
}
}
else{
if(Y>X+1)
{
len=(abs(2*X)-1)*(abs(2*X)-1);
len+=(Y-X)-1;
}
else
{
len=(abs(2*Y)+1)*(abs(2*Y)+1);
len-=(X-Y+1);
}
}
cout<<len;
return 0;
}