P16159 [ICPC 2016 NAIPC] Symmetry

ooliver 发布于 5 小时前 33 次阅读 OI

AI 摘要

当n个点混乱分布，只需添加最少对称点就能让它们完美对称，你想知道答案吗？本文巧用map枚举对称中心和对称轴，找出最小操作数。

P16159 [ICPC 2016 NAIPC] Symmetry

思路

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

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

我们 n2n^2 枚举每两个点。
对于对称中心，我们把两个点的中点添加到 map 里，并加一次贡献；
对于对称轴，我们把两个点的连线和两个点的中垂线添加到 map 里，连线不加贡献，中垂线加一次贡献。

统计答案时，我们枚举所有对称中心和对称轴。
对于对称中心，答案应该是 n-dot_map[i]*2-tag[i]，其中 dot_map[i] 是该点对应对称点的组数，tag[i] 是该点是否在初始点集中出现过。
对于对称轴，我们还需要一个循环找到在当前直线上的点的个数 cnt，答案就应该是 n-line_map[i]*2-cnt。
最终取最小答案输出即可。

细节

  1. 为了防止求中点时出现小数，我们在输入时全部乘二。
  2. 对于点的存储，直接哈希；对于直线的存储，我们用结构体存储其一般式 Ax+By+C=0Ax+By+C=0 中的三个常数，注意要存储最简形式（即最高项系数大于 0，并且三个数不可约）。
  3. 已知两点 (x1,y1),(x2,y2)(x1,y1),(x2,y2)，
    中点：(x1+x22,y1+y22)(\frac{x1+x2}{2},\frac{y1+y2}{2})；
    连线：(y1−y2)x+(x2−x1)y+(x1y2−x2y1)=0(y1-y2)x+(x2-x1)y+(x1y2-x2y1)=0；
    中垂线：2(x2−x1)x+2(y2−y1)y+(x12−x22+y12−y22)=02(x2-x1)x+2(y2-y1)y+(x1^2-x2^2+y1^2-y2^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;
}