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

数三角(编程题) - 题解

#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)
0 回复 0 转发 1 喜欢 7 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!