题解：P14308 【MX-S8-T1】斐波那契螺旋

ly_ld · 2025-10-25 19:23:15 · 题解

首先这题应该可以预处理，但蒟蒻没想到这样做，所以选择了直接模拟

设当前考虑到的正方形的左下角坐标是(x1,y1)，右上角坐标是(x2,y2)，边长是len，上一个矩形是(lx1,ly1)和(lx2,ly2)

因为矩形是逆时针旋转的，所以我们考虑四个方向：

• 当下一个矩形在上一个矩形的右边时，x1=lx2，y1=ly1
• 当下一个矩形在上一个矩形的上方时，x1=lx2-len，y1 = ly2
• 当下一个矩形在上一个矩形的左边时，x1=lx1-len，y1=ly2-len
• 当下一个矩形在上一个矩形的下方时，x1=lx1,y1=ly1-len

所以我们特判第一个和第二个正方形然后往后模拟，判断题目给的点是否在正方形内即可，判断到第一个覆盖该点的正方形即是答案

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll t;
ll x,y;

int main(){
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    cin >> t;

    while(t--){

        cin >> x >> y;

        ll x1 = -1;
        ll y1 = 0;
        ll x2 = 0;
        ll y2 = 1;

        if(x1<=x && x<=x2 && y1<=y && y<=y2){
            cout << 1<<endl;
            continue;
        }
        x1 = -1;
        y1 = -1;
        x2 = 0;
        y2 = 0;

        if(x1<=x && x<=x2 && y1<=y && y<=y2){
            cout << 1<<endl;
            continue;
        }
        ll lastlastlen = 1;
        ll lastlen = 1;
        ll len = 2;
        ll dir = 1;
        // dir : 1向右  2向上 3向左 4向下 
        while(!(x1<=x && x<=x2 && y1<=y && y<=y2)){
            len = lastlen + lastlastlen;

            switch(dir){
                case 1:
                    x1 = x2;
                    dir=2;
                    break;

                case 2:
                    y1 = y2;
                    x1 = x2-len;
                    dir=3;
                    break;

                case 3:
                    x1 = x1-len;
                    y1 = y2-len;
                    dir=4;
                    break;

                case 4:
                    y1 = y1-len;
                    dir=1;
                    break;

            }

            x2 = x1 + len;
            y2 = y1 + len;

            lastlastlen = lastlen;
            lastlen = len;

        }
        cout << len<<endl;

    }
}