数三角【蓝桥杯】/STL

数三角

STL

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

#include<iostream>
#include<vector>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int main()
{
    int n;
    cin>>n;
    //存储每个点
    vector<PII> v;
    //存储一个点出现的个数，这个后面是为了用find方法，还有删除边时需要用到个数
    map<PII,int> m;
    ll res=0;
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        v.push_back({x,y});
        m[{x,y}]++;
    }
    //遍历每个点作为顶点
    for(int i=0;i<v.size();i++)
    {
        int x1=v[i].first;
        int y1=v[i].second;
        //存储和每个边的距离平方的个数
        map<ll,int> ma;
        //存储出现过的距离的平方
        set<ll> pa;
        //存储要删除的
        int del=0;
        for(int j=0;j<v.size();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<<res<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57