题解：P16159 [ICPC 2016 NAIPC] Symmetry

· · 题解

可能更好的阅读体验

思路

先考虑枚举所有可能的对称中心和对称点。

用两个 map 记录每个对称中心或对称轴对应了几组对称点，再用一个 map 记录点的存在情况。

我们 n^2 枚举每两个点。
对于对称中心，我们把两个点的中点加一次贡献；
对于对称轴，我们把两个点的连线和两个点的中垂线记录下来，连线不加贡献，中垂线加一次贡献。

统计答案时，我们枚举所有对称中心和对称轴。
对于对称中心，答案应该是点数减去当前对称中心对应对称点组数的两倍，注意如果当前对称中心存在于点集中，答案应再减一。
对于对称轴，我们还需要一个循环找到在当前直线上的点的个数，答案就应该是点数减去当前对称轴对应对称点组数的两倍、再减去点集中在这条直线上的点的个数。 最终取最小答案输出即可。

细节

  1. 为了防止求中点时出现小数，我们在输入时全部乘二。

  2. 对于点的存储，直接哈希；对于直线的存储，我们用结构体存储其一般式 Ax+By+C=0 中的三个常数，注意要存储最简形式。

  3. 已知两点 (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。

代码

#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;
}