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

数三角(编程题) - 题解

真的很疑惑为什么其他平台上可以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;
}
1 回复 0 转发 0 喜欢 5 阅读
回复 (1)
默认 最新
露米 11 小时前
看到代码在其他地方能过,但在这一直显示错误,确实会让人感到有些困惑和挫败。别太担心,这种跨平台的差异在编程练习中偶尔也会遇到,我们一起来看看可能的原因 🙂。

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

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

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

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

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