P16159 [ICPC 2016 NAIPC] Symmetry
思路
先考虑枚举所有可能的对称中心和对称点。
用两个 map 记录每个对称中心或对称轴对应了几组对称点，再用一个 map 记录点的存在情况。
我们 枚举每两个点。
对于对称中心，我们把两个点的中点加一次贡献；
对于对称轴，我们把两个点的连线和两个点的中垂线记录下来，连线不加贡献，中垂线加一次贡献。
统计答案时，我们枚举所有对称中心和对称轴。
对于对称中心，答案应该是点数减去当前对称中心对应对称点组数的两倍，注意如果当前对称中心存在于点集中，答案应再减一。
对于对称轴，我们还需要一个循环找到在当前直线上的点的个数，答案就应该是点数减去当前对称轴对应对称点组数的两倍、再减去点集中在这条直线上的点的个数。
最终取最小答案输出即可。
细节
- 为了防止求中点时出现小数，我们在输入时全部乘二。
- 对于点的存储，直接哈希；对于直线的存储，我们用结构体存储其一般式 $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<bits/stdc++.h>
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<(const line& l1) const{
if(a!=l1.a) return a<l1.a;
if(b!=l1.b) return b<l1.b;
return c<l1.c;
}
};
map<int,int> d,tag;
map<line,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(a<0||(a==0&&b<0)) 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){
cout<<0;
return 0;
}
for(int i=1;i<=n;i++) cin>>x[i]>>y[i],x[i]<<=1,y[i]<<=1,tag[hsh(x[i],y[i])]=1;
for(int i=1;i<=n;i++) for(int j=i+1;j<=n;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;i<=n;i++) if(x[i]*ln.a+y[i]*ln.b+ln.c==0) cnt--;
ans=min(ans,cnt);
}
cout<<ans;
return 0;
}
Comments NOTHING