平面上有 n n个坐标相异的点,请问当中有多少组非共线的三个点,这三个点的 外心 也在这 nn 个点之中?

简介: 有一个正整数 nn 代表平面上的点数。接下来有 nn 行,当中的第 ii 行包含两个整数 x_i, y_i,xi​,yi​ 代表第 i 个点的坐标是 (x_i, y_i)(xi​,yi​)。


#include<cstring>
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 2e3+10;
typedef long long ll;
ll num[maxn];
struct node
{
    ll x,y;
}st[maxn];
ll distance(ll x1,ll y1,ll x2, ll y2)
{
    return ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
    int n ; 
    cin>>n;
    for(int i = 0 ; i< n ; i++)
    {
        cin>>st[i].x>>st[i].y;
    }
    ll sum = 0 ;
    for(int i = 0 ; i <n ;i ++)
    {
        map<ll,ll>mm;
        for(int j = 0 ; j<n  ; j++)
        {
            if(i!=j)
            {
                    ll s=distance(st[i].x,st[i].y,st[j].x,st[j].y);
                //    cout<<s<<endl;
                    mm[s]++;
            }
        }  

        map<ll,ll>::iterator it;  //遍历map写法

        for(it = mm.begin();it!=mm.end();it++)
        {
            if(it->second>=3)  
            {
                ll k = it->second;
            //    cout<<k<<endl;
                sum+=k*(k-1)*(k-2)/6;   //C k 3  
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}
目录
相关文章
|
4月前
|
C++
C++代码来计算一个点围绕另一个点旋转45度后的坐标
C++代码来计算一个点围绕另一个点旋转45度后的坐标
103 0
|
4月前
|
算法
平面中判断点在三角形内算法(同向法)
平面中判断点在三角形内算法(同向法)
30 0
|
4月前
|
算法 数据建模
平面中判断点在三角形内算法(重心法)
平面中判断点在三角形内算法(重心法)
49 0
|
4月前
|
算法 C++
空间或平面判断两线段相交(求交点)
空间或平面判断两线段相交(求交点)
26 0
|
4月前
|
算法 C++
平面中判断线段与矩形是否相交
平面中判断线段与矩形是否相交
70 0
二维平面的欧几里得距离
二维平面的欧几里得距离
|
7月前
|
算法
[Halcon&几何] 矩形顶点和对角连线角度计算
[Halcon&几何] 矩形顶点和对角连线角度计算
150 0
|
7月前
[Halcon&几何] 线段中点、端点和角度的计算
[Halcon&几何] 线段中点、端点和角度的计算
288 0
|
Java 索引
给定一个多边形的点集——判断所给点集的方向为顺时针方向还是逆时针方向【java实现+原理讲解】
给定一个多边形的点集——判断所给点集的方向为顺时针方向还是逆时针方向【java实现+原理讲解】
248 0
|
机器学习/深度学习
(模拟)(矩阵坐标表示)1219. 移动距离
(模拟)(矩阵坐标表示)1219. 移动距离
98 0