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

数三角(编程题) - 题解

真的很疑惑为什么其他平台上可以ac的代码这里是全错???



#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2005;
typedef pair<int,int>P;
int n,ans;
struct no
{
  int x,y;
}q[N];
map<P,int>mp;
int f(int i,int j)
{
  return (q[i].x-q[j].x)*(q[i].x-q[j].x)+(q[i].y-q[j].y)*(q[i].y-q[j].y);
}
signed main()
{
scanf("%lld",&n);
//1.map统计各个点出现次数
for(int i=1;i<=n;i++)
{
  scanf("%lld%lld",&q[i].x,&q[i].y);
  mp[{q[i].x,q[i].y}]++;
}
//2.开始枚举顶点
for(int i=1;i<=n;i++)
{
  map<int,vector<int>>st;
  for(int j=1;j<=n;j++)
  {
   int dis=f(i,j);
   if(dis)st[dis].push_back(j);//存储到i点距离为dis的点,分类
  }
  //计算合法的数量
  for(auto &x:st)
  {
    vector<int>&v=x.second;
    int sum=(int)v.size();
    ans+=sum*(sum-1)/2;
  
   //还要再看三点共线的
   int cnt=0;
   for(int j=0;j<sum;j++)//遍历这里相同距离的点
   {
     int x1=q[i].x,y1=q[i].y;//枚举的顶点
     int x2=q[v[j]].x,y2=q[v[j]].y;
     int x3=2*x1-x2,y3=2*y1-y2;
     cnt+=(mp[{x3,y3}]);//对于找到的这些点,取出其数量
   }
   ans-=(cnt/2);//因为重复计算了
  }
}
printf("%lld",ans);
  return 0;
}
2 回复 0 转发 0 喜欢 11 阅读
回复 (2)
默认 最新
露米 2026/2/20
x2`, which is the midpoint formula. This is correct for the case where the chosen vertex is the midpoint.

Let's write the response.

Acknowledge the frustration of platform differences.
Compliment the logic (it's a good approach).
Suggest checking the "equilateral triangle" count (common pitfall).
Suggest checking the "map" performance.
Suggest checking if the problem counts "ordered triplets" or "unique triangles".
End with an encouraging note
此外,还有一个容易被忽略的小细节:如果题目中给出的点集包含重复的坐标,目前的 mp[{x3, y3}] 统计方式可能会把重合的点也计算在内,这可能会导致计数出现偏差。你可以检查一下题目要求中是否保证了所有点坐标互不相同。

如果逻辑上确认无误,但依然全错,有时也可能是因为平台的时间限制非常严苛。在 $N=2000$ 的两层循环内频繁操作 map 和 `vector
0
露米 2026/2/4
看到代码在其他地方能过,但在这一直显示错误,确实会让人感到有些困惑和挫败。别太担心,这种跨平台的差异在编程练习中偶尔也会遇到,我们一起来看看可能的原因 🙂。

我仔细看了一下你的逻辑,思路其实很清晰,是通过枚举顶点并利用距离分类来统计等腰三角形的。不过,有几个小细节或许我们可以一起讨论一下:

  1. 重复计算的问题:目前的逻辑是枚举每一个顶点作为等腰三角形的“顶角”顶点。如果题目中出现了等边三角形,它会被三个顶点分别计算一次,这可能会导致最终的 ans 比预期要大。你可以确认一下题目是否要求对等边三角形做特殊的去重处理。

  1. 时间复杂度的常数:在 $N=2000$ 的循环内嵌套使用 map<int, vector<int>>,虽然在复杂度上是 $O(N^2 \log N)$,但 mapvector 的动态内存分配在一些时限较紧的平台上可能会造成压力。如果平台没有给出具体的 TLE(超时)而是统一显示全错,这也许是一个潜在的原因。

  1. 三点共线的处理:你现在的处理方式是减去了顶点作为中点的情况。可以再思考一下,是否存在其他三点共线且距离相等的情况需要排除?

你可以尝试先用一个小样本测试一下,看看输出结果是偏大还是偏小。如果需要的话,可以把题目的具体要求(比如对等边三角形的定义,或者具体的输入输出限制)再补充一下,我陪你一起再拆解看看~ 慢慢来就好。
0