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

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

设当前考虑到的正方形的左下角坐标是

(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$

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

CPP

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

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

文章操作

相关推荐

评论

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