Symmetry（对称轴）UVA 1595

你的名字 2024-02-17 18:49 21阅读 0赞

解题思路：本题的突破点在于通过最左边和最右边的点寻找对称轴，我的想法是利用set集合排序（由于用了结构体，故要重写<运算符），此时set集合中为从小到大，因为最右边x相同的点可能有多个（同一条轴上，但是最小的点是固定的），所有通过迭代器(last)向前遍历，直到y相同的点求得对称轴；接下来就好办了，使用迭代器遍历set集合中所有元素（因为是对称的，所以只需要找到n的一半对数就可以了(用count记数)）。

1.  \#include<cstdio>
2.  \#include<set>
3.  using namespace std;
4.  struct note\{ 
5.   int x,y;
6.   bool operator <(const note &n) const \{ 
7.   return x<n.x || x==n.x&&y<n.y; //set集合中用了结构体必须重写<运算符
8.   \}
9.  \};
10. set<note> set1;
11. int main()\{ 
12.  int T;
13.  scanf("%d",&T);
14.  while(T--)\{ 
15.  int n;
16.  scanf("%d",&n);
17.  note temp;
18.  for(int i=0;i<n;i++)
19.  \{ 
20.  scanf("%d%d",&temp.x,&temp.y);
21.  set1.insert(temp);
22.  \}
23.  int flag=1;
24.  set<note>::iterator first=set1.begin(),last=set1.end();
25.  last--;
26.  double sym=0;
27.  while(true)\{ //此循环用于寻找对称轴
28.  if((\*last).y != (\*first).y)last--;
29.  else \{ 
30.  sym=((\*first).x+(\*last).x)/(double)2; 
31.  break;\}
32.  \}
33.  int count1=0;
34.  for(;first!=set1.end();first++)\{ 
35.  note nt=\*first;
36.  nt.x=(int)(2\*sym)-nt.x; 
37.  if(set1.count(nt))count1++;
38.  else \{flag=0;
39.  break;\}
40.  if(count1>= n/2+1)break;
41.  \}
42.  if(flag)printf("YES\\n");
43.  else printf("NO\\n");
44.  set1.clear();
45.  \}
46.  return 0;
47. \}

发表评论取消回复

表情：

评论列表（有 0 条评论，21人围观）

还没有评论，来说两句吧...

相关阅读

相关第十一章模拟 17 AcWing 1595. 螺旋矩阵

第十一章模拟 17 AcWing 1595. 螺旋矩阵原题链接 [AcWing 1595. 螺旋矩阵][AcWing 1595.] 算法标签模拟

雨点打透心脏的1/2处/ 2024年03月31日 13:18/ 0 赞/ 51 阅读

相关 Symmetry（对称轴）UVA 1595

解题思路：本题的突破点在于通过最左边和最右边的点寻找对称轴，我的想法是利用set集合排序（由于用了结构体，故要重写<运算符），此时set集合中为从小到大，因为最右边x相同的点可

你的名字/ 2024年02月17日 18:49/ 0 赞/ 22 阅读

相关对称轴（Symmetry）

给出平面上N（N≤1000）个点，问是否可以找到一条竖线，使得所有点左右对称。 /对称轴一定是最左边和最右边点的中点所在竖线。可以找最左边和最右边的点,即横坐标最小

你的名字/ 2022年11月30日 04:28/ 0 赞/ 78 阅读

相关 HDU-1595&3986-枚举+最短路

find the longest of the shortest Time Limit: 1000/5000 MS (Java/Others) Memory Lim

忘是亡心i/ 2022年07月11日 12:11/ 0 赞/ 112 阅读

相关对称轴

The figure shown on the left is left-right symmetric as it is possible to fold the sheet

快来打我*/ 2022年06月12日 04:56/ 0 赞/ 90 阅读

相关 UVA 1595 Symmetry(暴力)

The figure shown on the left is left-right symmetric as it is possible to fold the sheet

男娘i/ 2022年06月07日 02:22/ 0 赞/ 133 阅读

相关 HDU-1595-find the longest of the shortest

find the longest of the shortest Time Limit: 1000/5000 MS (Java/Others) Memory Lim

太过爱你忘了你带给我的痛/ 2022年05月20日 10:41/ 0 赞/ 130 阅读

相关 Codeforces Round #127 (Div. 1) A. Clear Symmetry 打表

A. Clear Symmetry 题目连接： [http://codeforces.com/contest/201/problem/A][http_codef

布满荆棘的人生/ 2022年03月30日 05:08/ 0 赞/ 119 阅读

相关 fzu 2035 Axial symmetry(枚举+几何）

[题目链接：fzu 2035 Axial symmetry][fzu 2035 Axial symmetry] 题目大意：给出n个点，表示n边形的n个顶点，判断该n

旧城等待，/ 2021年11月19日 13:30/ 0 赞/ 158 阅读

相关 UVA 621

include<iostream> include<string> using namespace std; int main() {

朴灿烈づ我的快乐病毒、/ 2021年11月17日 21:33/ 0 赞/ 232 阅读