题目描述题目要求按顺时针螺旋顺序遍历平面上的整数点xxx表示分母yyy表示分子跳过分母为零的点x0x 0x0并且跳过约分后与之前重复的有理数。输出指定序号的有理数序号从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,…。方向顺序为右、下、左、上、右、…顺时针。跳过规则跳过x0x 0x0的点分母为零。跳过约分后与之前出现过的有理数重复的点。例如(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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);vectorpairint,intoffset{{0,1},{1,0},{0,-1},{-1,0}};setlonglongproduced{100001,1};mapint,pairint,intrational{{0,{1,1}},{1,{0,1}}};intnumber,max_number0;vectorintnumbers;while(cinnumber){numbers.push_back(number);max_numbermax(max_number,number);}intdirection0,counter2,startx0,starty0;queueintstep;step.push(1),step.push(1);while(countermax_number){intlengthOfStepstep.front();step.pop();for(inti1;ilengthOfStep;i){startxoffset[direction].first;startyoffset[direction].second;if(startx0||starty0)continue;intsign1;if(starty0)sign*-1;if(startx0)sign*-1;intnextyabs(starty),nextxabs(startx);intanexty,bnextx,t;while(a%b)ta,ab,bt%b;if(b0)nexty/b,nextx/b;if(produced.find(sign*(nexty*100000nextx))produced.end()){produced.insert(sign*(nexty*100000nextx));rational[counter]make_pair(sign*nexty,nextx);counter;}}direction1;direction%4;step.push(lengthOfStep1);}for(autoaNumber:numbers){pairint,intresutlrational[aNumber];coutresutl.first / resutl.second\n;}return0;}