数三角【蓝桥杯】/STL

码农世界 2024-05-18 前端 79 次浏览 0个评论

数三角

STL

思路：遍历每一个点，找到把这个点作为顶点，能构成的等腰三角形的个数，再将不合法的点删除

#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef pair PII;
int main()
{
    int n;
    cin>>n;
    //存储每个点
    vector v;
    //存储一个点出现的个数，这个后面是为了用find方法，还有删除边时需要用到个数
    map m;
    ll res=0;
    for(int i=0;i
        int x,y;
        cin>>x>>y;
        v.push_back({x,y});
        m[{x,y}]++;
    }
    //遍历每个点作为顶点
    for(int i=0;i
        int x1=v[i].first;
        int y1=v[i].second;
        //存储和每个边的距离平方的个数
        map ma;
        //存储出现过的距离的平方
        set pa;
        //存储要删除的
        int del=0;
        for(int j=0;j
            int x2=v[j].first;
            int y2=v[j].second;
            ll path=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
            if(!path) continue;
            pa.insert(path);
            //如果不能构成三角形，则说明三点共线，x1为中点，根据中点坐标公式推出x3和y3，如果找到了这样的点，则需要删除，且因为是对称的，所以最后要删的是del/2
            int x3=2*x1-x2;
            int y3=2*y1-y2;
            if(m.find({x3,y3})!=m.end()) del+=m[{x3,y3}];
            ma[path]++;
        }
        for(ll a:pa)
        {
            ll b=ma[a];
            res+=b*(b-1)/2;
        }
        res-=del/2;
    }
    cout<