返回题解分享
讨论 / 题解分享/ 帖子详情

数三角(编程题) - 题解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
#define endl '\n'
#define print(x) cout<<#x<<'='<<(x)<<endl;
int n;
const int N=3e3+5;
int x[N],y[N];
ll ans=0;
unordered_map<ll,ll> mp;
map<PII,int> vis;

ll dis(int i,int j)
{
    return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
    }
    for(int i=1;i<=n;i++)
    {

        mp.clear();
        vis.clear();
        for(int j=1;j<=n;j++)
        {
            if(i==j)
            {
                continue;
            }
            vis[{x[j],y[j]}]=1;
            mp[dis(i,j)]++;
            //(a,b),(x[j],y[j])的中点坐标是(x[i],y[i])
            int a=2*x[i]-x[j];
            int b=2*y[i]-y[j];
            if(mp[dis(i,j)]>=2)
            {
                if(vis[{a,b}]==1)//三点共线
                {
                    ans+=mp[dis(i,j)]-1-1;
                }
                else
                {
                    ans+=mp[dis(i,j)]-1;
                }
            }
        }
    }
    cout<<ans;
}


我觉得作者的数据是错的。我的代码可以在牛客上过掉69%(剩下的是因为超时,但是我感觉o(n^2)的应该可以呀),但是在本网站上就是WA。牛客上的原题:等腰三角形(hard) (nowcoder.com)
3 回复 0 转发 1 喜欢 15 阅读
回复 (3)
默认 最新
露米 5 小时前
看到你还在努力调试,这种不放弃的劲头真的很让人佩服 🙂

关于你提到的 WA 和超时,我刚才又帮你想了一下。如果调整了统计顺序后还是没过,或许可以试试把内层循环里的 unordered_map 换成一个简单的数组。因为 $N$ 是 3000,我们可以先算出所有距离存进 vector 里,排序后再统一计数,这样能省掉很多哈希计算的时间,说不定就能在牛客上跑通剩下的 31% 了。

至于本站的 WA,如果逻辑上已经排除了顺序影响,我们可以一起看看是不是在计算 2*x[i]-x[j] 时,坐标的范围或者负数情况对 vis 的判断产生了干扰?

你可以先挑其中一个小点尝试改改看,不用给自己太大压力,一点点排查总能找到那个“小顽皮”的 Bug。如果改动后结果有了变化,记得回来分享一下呀,我很期待你的进展。
0
露米 2026/2/5
我看到你艾特我了,我也一直在关注你的进度呢 🙂

关于你提到的数据问题,我非常理解这种在不同平台结果不一致时的困惑。不过在怀疑数据之前,我们再一起看一个小细节好吗?

在目前的内层循环中,判断共线的逻辑是 if(vis[{a,b}]==1)。因为 vis 是在循环过程中动态填充的,如果点 $(a, b)$ 出现在当前点 $j$ 的“后面”,这一步可能就没法正确识别出共线了。这或许就是导致 WA 的原因,因为统计的结果会受到输入点顺序的影响。

你可以试着先把当前顶点 $i$ 对应的所有点信息记录完整,或者在统计前先对坐标进行统一处理,保证判断逻辑的稳定性,看看结果会不会有变化?

至于超时,确实如你所感,$O(n^2)$ 在 $N=3000$ 时是合理的,只是内层的 map 确实运行得有点辛苦。如果逻辑理顺了,我们可以再一起想办法优化常数项。

别灰心,这种调试过程虽然磨人,但也是提升最快的时候。你觉得这个统计顺序的小差异,会不会是导致问题的关键呢?
0
露米 2026/2/5
看到你在不同平台上反复测试、寻找差异,这种钻研精神真的很棒呢 🙂

关于在本站遇到 WA(答案错误),我有一个小小的建议供你参考:

在你的代码逻辑里,ans 是在内层循环中动态累加的。这种方式在处理“三点共线”的扣除时,逻辑会变得比较复杂,容易因为统计的先后顺序导致多减或少减。

通常这类题目,如果固定一个顶点 $i$,可以尝试先统计出所有距离相等的点(比如用一个临时的数组或者哈希表记录频次 $k$),那么初步的组合数就是 $k(k-1)/2$。之后再统一减去那些以 $i$ 为中点的共线情况,逻辑可能会更清晰一些,也不容易出错。

另外,关于超时的问题,$N=3000$ 的 $O(n^2)$ 确实是标准解法,但 std::map 带有 $\log$ 且常数较大,在内层循环里频繁 clear 和插入可能会消耗不少时间。如果把 vis 换成更轻量的数据结构,或许就能顺利通过牛客剩下的测试点了。

你可以尝试调整一下统计的时机看看吗?如果调整后还是有问题,我们可以再一起看看具体的逻辑细节。加油,离 AC 已经很近了!
0