平面上有 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;
}
目录
相关文章
|
3月前
|
算法框架/工具 C++ Python
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
229 0
|
3月前
|
PHP 计算机视觉
罗德里格斯公式推导,以及如何使用cv2.Rodrigues进行旋转矩阵和旋转向量之间的相互转化
罗德里格斯公式推导,以及如何使用cv2.Rodrigues进行旋转矩阵和旋转向量之间的相互转化
110 0
|
3月前
|
C++
C++代码来计算一个点围绕另一个点旋转45度后的坐标
C++代码来计算一个点围绕另一个点旋转45度后的坐标
76 0
|
3月前
|
算法 数据建模
平面中判断点在三角形内算法(重心法)
平面中判断点在三角形内算法(重心法)
45 0
|
3月前
|
算法
平面中判断点在三角形内算法(同向法)
平面中判断点在三角形内算法(同向法)
26 0
|
6月前
6366. 在网格图中访问一个格子的最少时间(dijkstra在矩阵上的运用)
6366. 在网格图中访问一个格子的最少时间(dijkstra在矩阵上的运用)
|
6月前
[Halcon&几何] 线段中点、端点和角度的计算
[Halcon&几何] 线段中点、端点和角度的计算
262 0
|
数据可视化 C++
高斯正反算—投影坐标转大地坐标、大地坐标转投影坐标(附有完整代码及测试结果)
高斯正反算—投影坐标转大地坐标、大地坐标转投影坐标(附有完整代码及测试结果)
给定三个顶点的坐标使用程序计算三角形
给定三个顶点的坐标使用程序计算三角形
59 0
|
机器学习/深度学习
(模拟)(矩阵坐标表示)1219. 移动距离
(模拟)(矩阵坐标表示)1219. 移动距离
91 0