核心内容摘要
西溪，不止山河，更在人文
题目分析本题模拟了一个简单的窗口系统需要处理鼠标点击事件根据点击位置确定选中的区域Region \texttt{Region}Region或图标Icon \texttt{Icon}Icon。
关键规则如果点击位置在某个区域内包括边界则选中该区域。
如果点击位置不在任何区域内则选中距离最近的可见图标如果多个图标距离相同则全部选中。
区域会遮挡图标被区域完全覆盖的图标视为不可见。
区域按输入顺序标记为A、B、…图标按输入顺序编号为
1、
…。
当多个区域重叠时后输入的区域视为在前面即覆盖先输入的区域。
输入格式每行以一个大写字母开头表示数据类型I表示图标后跟其中心坐标( x , y ) (x, y)(x,y)。
R表示区域后跟左上角( x 1 , y 1 ) (x_1, y_
(x1,y1)和右下角( x 2 , y 2 ) (x_2, y_
(x2,y2)坐标。
M表示鼠标点击后跟点击坐标( x , y ) (x, y)(x,y)。
第一个M之后不会再出现I或R。
输入以#结束。
输出格式对于每个鼠标点击输出一行表示选中的区域或图标区域输出单个大写字母。
图标输出其编号宽3 33位、右对齐若多个图标按编号升序输出。
解题思路数据结构设计图标Icon \texttt{Icon}Icon存储其中心坐标、编号、到当前点击点的距离、是否可见。
区域Region \texttt{Region}Region存储其矩形范围左上角和右下角坐标、字母标签。
处理流程读入所有I和R数据分别存入向量中。
遇到M时a.判断是否点击在区域内从后往前遍历区域向量后输入的在前若点击坐标在某个矩形内含边界则选中该区域输出其标签并跳过后续图标处理。
b.若不在任何区域内计算每个图标到点击点的欧几里得距离平方避免开方比较时等价。
判断每个图标是否可见若其中心被任何一个区域覆盖则不可见。
对图标按可见性优先、距离次之、编号最小排序。
输出所有可见且距离等于最小距离的图标编号按格式右对齐、宽3 33位。
注意事项区域遮挡关系后输入的区域在前因此判断图标可见性时应遍历所有区域只要被任意一个区域覆盖即不可见。
图标距离计算使用平方距离即可无需开方。
输出格式图标编号需右对齐、占3 33位多个图标按编号升序排列排序已保证。
代码实现// Mouse Clicks// UVa ID: 142// Verdict: Accepted// Submission Date:
// UVa Run Time:
012s//// 版权所有C2016邱秋。
metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structicon{intleftX,topY;intlabel;intdistance;intvisible;};structregion{intleftX,topY,rightX,bottomY;charlabel;};// 图标排序比较规则booloperator(consticona,consticonb){if(a.visibleb.visible){if(a.distanceb.distance)returna.labelb.label;elsereturna.distanceb.distance;}elsereturna.visibleb.visible;}intmain(){string line;string category;intleftX,topY,rightX,bottomY;vectoriconicons;vectorregionregions;intindexI1,indexR1;while(getline(cin,line),line!#){istringstreamiss(line);isscategoryleftXtopY;if(line.find(I)!line.npos){icons.push_back((icon){leftX,topY,indexI,0,0});}elseif(line.find(R)!line.npos){issrightXbottomY;regions.push_back((region){leftX,topY,rightX,bottomY,(AindexR-