AcWing 1237. 螺旋折线
原题链接
中等
作者:
Value
,
2020-04-26 11:12:08
,
所有人可见
,
阅读 657
一个一个模拟:超时
// 模拟
#include <iostream>
using namespace std;
typedef long long ll;
int x, y;
int a;
int b;//起始位置
int isFit(int xx, int yy){
if(xx == a){// 纵向
if(x != a) return -1;
int sm = max(yy, b);
int xm = yy + b - sm;
if(y >= xm && y <= sm){
return abs(y-b);
}else{
return -1;
}
}else if(yy == b){ //横向
if(y != b) return -1;
int yb = max(a, xx);
int zb = a + xx - yb;
if(x >= zb && x <= yb){
return abs(x-a);
}else{
return -1;
}
}else{
return -1;
}
}
int dy[4] = {0, 1, 0, -1};
int dx[4] = {-1, 0, 1, 0};//左 上 右 下
int main(){
cin >> x >> y;
ll sum = 0;
for(int i = 0; ; i ++ ){ // 走的次数
//从第0 次开始 ,走的步数(i/2 + 1),方向i%4
int xx = a + dx[i%4]*(i/2+1);
int yy = b + dy[i%4]*(i/2+1);
int res = isFit(xx, yy);
if(res != -1){ //在这条直线上面
sum += res;
break;
}else{
sum += i/2+1;
a = xx;
b = yy;
}
}
cout << sum << endl;
return 0;
}
找规律
#include <iostream>
using namespace std;
typedef long long ll;
int main(){
int x, y;
cin >> x >> y;
//判断在哪个方向上的边
ll sum = 0;
if(y >= abs(x)){ //上
//端点 y >= 0
int n = y;
sum = ((ll)2*n*(2*n-1)) + x + n;
}else if(x >= abs(y)){ //左
int n = x;
sum = ((ll)4*n*n) + n - y;
}else if(-y+1 >= -x){ //下
int n = -y;
sum = (ll)2*n*(2*n+1) + n - x;
}else{
//x <= 0
int n = abs(x);
sum = (ll)(2*n-1)*(2*n-1) + y + n - 1;
}
cout << sum << endl;
return 0;
}