题目描述
题目要求按顺时针螺旋顺序遍历平面上的整数点（xxx表示分母，yyy表示分子），跳过分母为零的点（x=0x = 0x=0），并且跳过约分后与之前重复的有理数。输出指定序号的有理数（序号从000开始）。输出格式为分子 / 分母，且分母必须为正，符号在分子上。
输入格式
输入包含多个整数，每行一个，表示需要输出的有理数的序号。输入以文件结束符（EOF\texttt{EOF}EOF）终止。
输出格式
对于每个输入的序号，输出一行，格式为分子 / 分母。
样例
输入
0 1 2 3 10输出
1 / 1 0 / 1 -1 / 1 -2 / 1 3 / 2题目分析
本题的核心是模拟顺时针螺旋遍历整数网格，并收集不重复的有理数。
螺旋遍历
从原点(0,0)(0,0)(0,0)开始，顺时针螺旋向外移动。步长序列为：1,1,2,2,3,3,4,4,…1,1,2,2,3,3,4,4,\ldots1,1,2,2,3,3,4,4,…。方向顺序为：右、下、左、上、右、…（顺时针）。
跳过规则
- 跳过x=0x = 0x=0的点（分母为零）。
- 跳过约分后与之前出现过的有理数重复的点。例如(4,2)(4,2)(4,2)约分为(2,1)(2,1)(2,1)，若(2,1)(2,1)(2,1)之前已出现，则跳过。
- 跳过(0,0)(0,0)(0,0)点（不是有理数）。
有理数标准化
为方便去重，将每个有理数标准化为分母为正的最简形式：
- 分子分母同取绝对值，用最大公约数约分。
- 若分子为负，则整体符号放在分子上，分母保持为正。
使用一个集合存储已出现的有理数，用编码分子 * 100000 + 分母或分子 * 100000 + 分母作为唯一标识（注意正负号单独处理）。
生成过程
- 初始化：第000个有理数为(1,1)(1,1)(1,1)，第111个有理数为(0,1)(0,1)(0,1)（注意原点(0,0)(0,0)(0,0)被跳过，(0,1)(0,1)(0,1)对应0/10/10/1）。
- 然后继续螺旋遍历，收集后续有理数，直到达到所需的最大序号。
复杂度分析
需要生成到最大序号对应的有理数，序号可能较大，但生成速度足够。
代码实现
// Rational Spiral// UVa ID: 493// Verdict: Accepted// Submission Date: 2016-07-29// UVa Run Time: 0.580s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);vector<pair<int,int>>offset={{0,1},{1,0},{0,-1},{-1,0}};set<longlong>produced={100001,1};map<int,pair<int,int>>rational={{0,{1,1}},{1,{0,1}}};intnumber,max_number=0;vector<int>numbers;while(cin>>number){numbers.push_back(number);max_number=max(max_number,number);}intdirection=0,counter=2,startx=0,starty=0;queue<int>step;step.push(1),step.push(1);while(counter<=max_number){intlengthOfStep=step.front();step.pop();for(inti=1;i<=lengthOfStep;i++){startx+=offset[direction].first;starty+=offset[direction].second;if(startx==0||starty==0)continue;intsign=1;if(starty<0)sign*=-1;if(startx<0)sign*=-1;intnexty=abs(starty),nextx=abs(startx);inta=nexty,b=nextx,t;while(a%b)t=a,a=b,b=t%b;if(b>0)nexty/=b,nextx/=b;if(produced.find(sign*(nexty*100000+nextx))==produced.end()){produced.insert(sign*(nexty*100000+nextx));rational[counter]=make_pair(sign*nexty,nextx);counter++;}}direction+=1;direction%=4;step.push(lengthOfStep+1);}for(autoaNumber:numbers){pair<int,int>resutl=rational[aNumber];cout<<resutl.first<<" / "<<resutl.second<<'\n';}return0;}
