P16159 [ICPC 2016 NAIPC] Symmetry

2026年4月26日 ooliver OI

P16159 [ICPC 2016 NAIPC] Symmetry

思路

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

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

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

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

细节

为了防止求中点时出现小数，我们在输入时全部乘二。
对于点的存储，直接哈希；对于直线的存储，我们用结构体存储其一般式 $A x + B y + 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_{1} y_{2} - x_{2} y_{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;
}`