平面上有 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;
}
目录
相关文章
|
5月前
[Halcon&几何] 线段中点、端点和角度的计算
[Halcon&几何] 线段中点、端点和角度的计算
61 0
|
5月前
|
算法
[Halcon&几何] 矩形顶点和对角连线角度计算
[Halcon&几何] 矩形顶点和对角连线角度计算
38 0
二维平面的欧几里得距离
二维平面的欧几里得距离
|
Python
点云在任意平面上获取二维投影
点云在任意平面上获取二维投影
930 0
点云在任意平面上获取二维投影
|
11月前
|
数据可视化 C++
高斯正反算—投影坐标转大地坐标、大地坐标转投影坐标(附有完整代码及测试结果)
高斯正反算—投影坐标转大地坐标、大地坐标转投影坐标(附有完整代码及测试结果)
|
11月前
|
Java 索引
给定一个多边形的点集——判断所给点集的方向为顺时针方向还是逆时针方向【java实现+原理讲解】
给定一个多边形的点集——判断所给点集的方向为顺时针方向还是逆时针方向【java实现+原理讲解】
151 0
|
机器学习/深度学习
(模拟)(矩阵坐标表示)1219. 移动距离
(模拟)(矩阵坐标表示)1219. 移动距离
66 0
|
PyTorch 算法框架/工具
【pytorch实现】用卷积核检测图中对角方向边缘(小练习)
【pytorch实现】用卷积核检测图中对角方向边缘(小练习)
|
算法
【平面解析几何】直线方程的表示形式
【平面解析几何】直线方程的表示形式
184 0
平面上给定n条线段,找出一个点,使这个点到这n条线段的距离和最小。
题目:平面上给定n条线段,找出一个点,使这个点到这n条线段的距离和最小。 源码如下: 1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 ...
1064 0