P16159 [ICPC 2016 NAIPC] Symmetry 思路 先考虑枚举所有可能的对称中心和对称点。 用两个 map 记录每个对称中心或对称轴对应了几组对称点，再用一个 map 记录点的存在情况。 我们 n2n^2 枚举每两个点。 对于对称中心，我们把两个点的中点加一次贡献； 对于对称轴，我们把两个点的连线和两个点的中垂线记录下来，连线不加贡献，中垂线加一次贡献。 统计答案时，我们枚举所有对称中心和对称轴。 对于对称中心，答案应该是点数减去当前对称中心对应对称点组数的两倍，注意如果当前对称中心存在于点集中，答案应再减一。 对于对称轴，我们还需要一个循环找到在当前直线上的点的个数，答案就应该是点数减去当前对称轴对应对称点组数的两倍、再减去点集中在这条直线上的点的个数。 最终取最小答案输出即可。 细节 为了防止求中点时出现小数，我们在输入时全部乘二。 对于点的存储，直接哈希；对于直线的存储，我们用结构体存储其一般式 Ax+By+C=0 中的三个常数，注意要存储最简形式。 已知两点 (x_1,y_1),(x_2,y_2)， 中点：(\frac{x_1+x_2}{2},\frac{y_1+y_2}{2})； 连线：(y_1−y_2)x+(x_2−x_1)y+(x_1y_2−x_2y_1)=0； 中垂线：2(x_2-x_1)x+2(y_2-y_1)y+(x_1^2-x_2^2+y_1^2-y_2^2)=0。 代码： C++ #include using namespace std; #define int long long #define fi first #define sc second const int N=1e3+5; int n,ans=INT_MAX; int x[N],y[N]; struct line{ int a,b,c; bool operator d,tag; map l; int hsh(int xx,int yy){return xx*100000+yy;} line func(int a,int b,int c){ int g=__gcd(__gcd(a,b),c); a/=g,b/=g,c/=g; if(a>1,y1+y2>>1)]++; l[func(a1,b1,c1)]++,l[func(a2,b2,c2)]+=0; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n; if(n==1){ cout>x[i]>>y[i],x[i] `#include using namespace std; #define int long long #define fi first #define sc second const int N=1e3+5; int n,ans=INT_MAX; int x[N],y[N]; struct line{ int a,b,c; bool operatorconst line& l1) const{ if(a!=l1.a) return al1.a; if(b!=l1.b) return bl1.b; return cl1.c; } }; map,int> d,tag; mapline,int> l; int hsh(int xx,int yy){return xx*100000+yy;} line func(int a,int b,int c){ int g=__gcd(__gcd(a,b),c); a/=g,b/=g,c/=g; if(a0||(a==0&&b0)) a=-a,b=-b,c=-c; return {a,b,c}; } void add(int x1,int y1,int x2,int y2){ int a1=(x2-x1)1,b1=(y2-y1)1,c1=x1*x1-x2*x2+y1*y1-y2*y2; int a2=y1-y2,b2=x2-x1,c2=x1*y2-x2*y1; d[hsh(x1+x2>>1,y1+y2>>1)]++; l[func(a1,b1,c1)]++,l[func(a2,b2,c2)]+=0; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n; if(n==1){ cout0; return 0; } for(int i=1;in;i++) cin>>x[i]>>y[i],x[i]1,y[i]1,tag[hsh(x[i],y[i])]=1; for(int i=1;in;i++) for(int j=i+1;jn;j++) add(x[i],y[i],x[j],y[j]); for(auto u:d) ans=min(ans,n-u.sc*2-tag[u.fi]); for(auto u:l){ int cnt=n-u.sc*2; line ln=u.fi; for(int i=1;in;i++) if(x[i]*ln.a+y[i]*ln.b+ln.c==0) cnt--; ans=min(ans,cnt); } coutans; return 0; }`
P16159 [ICPC 2016 NAIPC] Symmetry
笔记