Menu
Article

【CodeForces 886F】Symmetric Projections / 题解

Zepto

Zepto

• 2 min read

题目描述

给定一个二维平面的点集。一条经过原点的直线被称作好的直线，当且仅当点集内每个点到这条直线的投影呈中心对称。请找出好的直线的总条数。

输入

第一行输入点集大小 $n \ (1\leq n\leq 2000)$；

接下来的 $n$ 行每行两个整数 $x_i,\ y_i \ (-10^6 \leq x_i, \ y_i \leq 10^6)$，表示，每个点的坐标。点的坐标互不相同。

输出

如果存在无数条好的直线，输出 $-1$；

否则，输出一个整数 – 好直线的数量。

思路

首先，我们知道直线上这些点的对称中心一定是原点集重心在直线上的投影。

那么我们首先枚举每对点，如果发现它们的中点都是重心，那么满足条件的直线就有无数条。

否则，我们直接枚举和第一个点对称的点，每次枚举都唯一确定了一条直线 $vec$。接下来我们使用点积计算每个点在这条直线上的投影长度，排序后判断即可。

如何计算 vec：对于确定的点对 $U, \ V$，它们的中点 $P$ 到直线的投影一定和重心 $R$的投影相同，于是有向量 $\overrightarrow{RP} \perp \overrightarrow{vec}$。

代码

#include 
#define maxn 2010
#define mp make_pair
#define eps 1e-9
using namespace std;
int n,id[maxn],x,ans;
struct Node{
    double x,y;
    Node (double a=0,double b=0){
        x=a,y=b;
    }
    Node operator + (Node a){
        return Node(x+a.x,y+a.y);
    }
    Node operator - (Node a){
        return Node(x-a.x,y-a.y);
    }
    Node operator / (double a){
        return Node(x/a,y/a);
    }
    double operator * (Node a){
        return x*a.x+y*a.y;
    }
    bool operator == (Node a){
        return fabs(x-a.x) a[maxn];
bool check(int pos){
    mid=(p[x]+p[pos])/2;
    vec=root-mid;
    vec=Node(vec.y,-vec.x);
    for (register int i=1;i<=n;++i)
        a[i]=mp(vec*p[i],i);
    sort(a+1,a+1+n);
    for (register int i=1;i<=n;++i)
        id[a[i].second]=i;
    if (id[x]+id[pos]!=n+1) return 0;
    double cmp=a[1].first+a[n].first;
    for (register int i=1;i<=n;++i)
        if (fabs(a[i].first+a[n-i+1].first-cmp)>eps) return 0;
    return 1;
}
int main(){
    scanf("%d",&n);
    for (register int i=1,a,b;i<=n;++i)
        scanf("%lf%lf",&a,&b),p[i]=Node(a,b),
        root=root+p[i];
    root=root/n;
    for (register int i=1;i<=n;++i){
        bool sub=0;
        for (register int j=1;j<=n;++j)
            if (p[i]+p[j]==root+root) sub=1;
        if (!sub) x=i;
    }
    if (!x) return puts("-1"),0;
    for (register int i=1;i<=n;++i)
        if (check(i)) ans++;
    printf("%d",ans);
}

后话

在讲题人讲题爆出原题题号之前，这道题在 CodeForces 上只有不到 30 人通过，感觉是一道奇难无比的毒瘤题。写完以后回顾代码，似乎也没那么麻烦。但是这个 $\Theta(n)$ 的枚举，以及利用点积的 $\Theta(n\log n)$ 判断，我在考场上一定想不到，就算想到了也写不出来。所以你别看我博客里文章都写得漂漂亮亮的，其实这个糟老头菜得很。

Share