题目描述题目模拟了一个二维平面上的齿轮系统。齿轮安装在300×300300 \times 300300×300的网格点上坐标范围111到300300300每个齿轮有内半径靠近板面和外半径远离板面。齿轮绕其中心旋转当两个齿轮接触时内半径相切或外半径相切它们会以相等的线速度驱动对方。系统中有一个马达齿轮motor gear\texttt{motor gear}motor gear是唯一的动力来源以给定的转速RPM\texttt{RPM}RPM旋转。需要计算其他齿轮的旋转方向和转速并检测以下错误和警告重叠错误Error -- Overlapping Gears\texttt{Error -- Overlapping Gears}Error -- Overlapping Gears两个或更多齿轮在内半径或外半径处发生重叠即圆心距小于两半径之和。冲突错误Error -- Conflicting Gear Rotation\texttt{Error -- Conflicting Gear Rotation}Error -- Conflicting Gear Rotation某个齿轮被两个不同的转速驱动即通过不同路径到达同一齿轮时计算出的转速不一致。空闲警告Warning -- Idle Gear\texttt{Warning -- Idle Gear}Warning -- Idle Gear某个齿轮的转速为零未被驱动。输入格式输入包含多组配置每组配置的格式如下第一行包含六个整数马达的xxx、yyy坐标内半径iririr、外半径ororor转速AVAVAV负数表示逆时针正数表示顺时针以及齿轮数量NGNGNG1≤NG≤201 \le NG \le 201≤NG≤20不包括马达。接下来NGNGNG行每行包含四个整数齿轮的xxx、yyy坐标内半径iririr和外半径ororor。所有坐标和半径均为整数范围111到300300300坐标或111到100100100半径转速绝对值111到100010001000。输出格式对于每组配置首先输出一行Simulation #X其中XXX从111开始递增左对齐从第131313列开始。如果没有错误输出NGNGNG行不包括马达每行格式为齿轮编号右对齐占222列、冒号第333列、方向第555列L表示逆时针R表示顺时针、转速从第777列开始左对齐保留两位小数。如果某齿轮转速为零输出Warning -- Idle Gear从第555列到第242424列。如果有错误只输出两行第一行为Simulation #X第二行为错误信息左对齐从第111列开始。重叠错误优先于冲突错误。每组输出后跟一个空行。样例输入20 100 5 5 -300 5 43 100 18 10 43 74 8 4 71 100 10 15 94 100 3 8 122 100 25 6 20 100 5 5 -300 5 43 100 18 10 43 74 8 4 71 100 10 10 89 100 3 8 105 100 25 6 20 100 5 5 -300 5 43 100 18 10 43 74 8 4 71 100 10 10 89 100 3 8 125 100 25 6输出Simulation #1 1: R 83.33 2: L 187.50 3: L 150.00 4: R 281.25 5: L 33.75 Simulation #2 Error -- Overlapping Gears Simulation #3 1: R 83.33 2: L 187.50 3: L 150.00 4: R 187.50 5: Warning -- Idle Gear题目分析本题的核心是建立齿轮之间的接触关系图然后从马达齿轮开始进行广度优先遍历BFS\texttt{BFS}BFS计算每个齿轮的转速和方向同时检测重叠、冲突和空闲情况。齿轮接触判定两个齿轮iii和jjj的圆心距为d(xi−xj)2(yi−yj)2 d \sqrt{(x_i - x_j)^2 (y_i - y_j)^2}d(xi​−xj​)2(yi​−yj​)2​接触条件内半径接触diriirjd ir_i ir_jdiri​irj​精度允许10−610^{-6}10−6误差外半径接触doriorjd or_i or_jdori​orj​如果diriirjd ir_i ir_jdiri​irj​或doriorjd or_i or_jdori​orj​则发生重叠错误。转速计算当两个齿轮接触时接触点的线速度相等。设齿轮iii的转速为viv_ivi​RPM\texttt{RPM}RPM半径为rir_iri​接触时使用的半径则线速度为vi×riv_i \times r_ivi​×ri​。对于齿轮jjj有vi×rivj×rj v_i \times r_i v_j \times r_jvi​×ri​vj​×rj​因此vjrirj×vi v_j \frac{r_i}{r_j} \times v_ivj​rj​ri​​×vi​接触类型决定了使用的半径内半径接触使用内半径iririr外半径接触使用外半径ororor方向规则当两个齿轮通过内半径接触时旋转方向相反通过外半径接触时旋转方向也相反。因此无论哪种接触相邻齿轮的方向始终相反。设马达的转速符号为负表示逆时针L\texttt{L}L正表示顺时针R\texttt{R}R。遍历时每经过一条边方向取反。冲突检测如果某个齿轮已经被访问过再次通过另一条路径到达时新计算出的方向必须与已记录的方向一致新计算出的转速绝对值必须与已记录的转速相等误差10−610^{-6}10−6内若任一条件不满足则产生冲突错误。重叠错误的优先级题目明确指出重叠错误优先于冲突错误。因此检测顺序为先检查所有齿轮对是否存在重叠若有则直接输出重叠错误不再进行后续的转速计算。空闲齿轮遍历结束后转速为零的齿轮未被任何齿轮驱动或虽然被驱动但计算出的转速为零应输出空闲警告。注意马达齿轮本身不输出。代码实现// Gears on a Board// UVa ID: 407// Verdict: Accepted// Submission Date: 2016-08-06// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constdoubleepsilon1e-6;structgear{intindex;doublex,y,gir,gor;boolis_rotate_left;doublevelocity;};structadjacent{intindex;boolir_touched,or_touched;};intcases0,ng;vectorgeargears;vectorvectoradjacentedges;voidrun(){coutSimulation #cases\n;edges.assign(ng,vectoradjacent());for(inti0;ing;i)for(intji1;jng;j){adjacent edge;edge.indexj,edge.ir_touchedfalse,edge.or_touchedfalse;doubledsqrt(pow(gears[i].x-gears[j].x,2)pow(gears[i].y-gears[j].y,2));if(dgears[i].girgears[j].gir-epsilon||dgears[i].gorgears[j].gor-epsilon){coutError -- Overlapping Gears\n\n;return;}if(fabs(d-gears[i].gir-gears[j].gir)epsilon)edge.ir_touchedtrue;if(fabs(d-gears[i].gor-gears[j].gor)epsilon)edge.or_touchedtrue;if(edge.ir_touched||edge.or_touched){edges[i].push_back(edge);edge.indexi;edges[j].push_back(edge);}}vectorboolvisited(ng,false);queueintunvisited;unvisited.push(0);visited[0]true;while(unvisited.empty()false){intcurrentunvisited.front();unvisited.pop();boolis_rotate_left!gears[current].is_rotate_left;for(autoedge:edges[current]){doublefinal_velocity,ir_velocity-1.0,or_velocity-1.0;if(edge.ir_touched){ir_velocitygears[current].gir/gears[edge.index].gir*gears[current].velocity;final_velocityir_velocity;}if(edge.or_touched){or_velocitygears[current].gor/gears[edge.index].gor*gears[current].velocity;final_velocityor_velocity;}if(ir_velocity0or_velocity0fabs(ir_velocity-or_velocity)epsilon){coutError -- Conflicting Gear Rotation\n\n;return;}if(visited[edge.index]false){gears[edge.index].is_rotate_leftis_rotate_left;gears[edge.index].velocityfinal_velocity;visited[edge.index]true;unvisited.push(edge.index);}else{if(gears[edge.index].is_rotate_left!is_rotate_left||fabs(gears[edge.index].velocity-final_velocity)epsilon){coutError -- Conflicting Gear Rotation\n\n;return;}}}}for(inti1;ing;i){cout i: ;if(fabs(gears[i].velocity)epsilon){coutWarning -- Idle Gear\n;continue;}cout(gears[i].is_rotate_left?L:R);cout fixedsetprecision(2)gears[i].velocity;cout\n;}cout\n;}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);doublex,y,gir,gor,velocity;gear motor;while(cinmotor.xmotor.ymotor.girmotor.gormotor.velocityng){gears.clear();motor.is_rotate_leftmotor.velocity0;motor.velocityfabs(motor.velocity);gears.push_back(motor);for(inti1;ing;i){cinxygirgor;gears.push_back((gear){i,x,y,gir,gor,false,0.0});}ng;run();}return0;}