平面上有 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;
}
目录
相关文章
|
2月前
6366. 在网格图中访问一个格子的最少时间(dijkstra在矩阵上的运用)
6366. 在网格图中访问一个格子的最少时间(dijkstra在矩阵上的运用)
|
2月前
[Halcon&几何] 线段中点、端点和角度的计算
[Halcon&几何] 线段中点、端点和角度的计算
133 0
|
2月前
|
算法
[Halcon&几何] 矩形顶点和对角连线角度计算
[Halcon&几何] 矩形顶点和对角连线角度计算
60 0
|
数据可视化 C++
高斯正反算—投影坐标转大地坐标、大地坐标转投影坐标(附有完整代码及测试结果)
高斯正反算—投影坐标转大地坐标、大地坐标转投影坐标(附有完整代码及测试结果)
|
算法
巧解“求取矩形面积划分”
巧解“求取矩形面积划分”
81 0
给定三个顶点的坐标使用程序计算三角形
给定三个顶点的坐标使用程序计算三角形
41 0
|
机器学习/深度学习
(模拟)(矩阵坐标表示)1219. 移动距离
(模拟)(矩阵坐标表示)1219. 移动距离
74 0
|
PyTorch 算法框架/工具
【pytorch实现】用卷积核检测图中对角方向边缘(小练习)
【pytorch实现】用卷积核检测图中对角方向边缘(小练习)
|
算法
【平面解析几何】直线方程的表示形式
【平面解析几何】直线方程的表示形式
193 0
|
C#
用动画的方式画出任意的路径(直线、曲线、折现)
原文:用动画的方式画出任意的路径(直线、曲线、折现) 版权声明:本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。欢迎转载、使用、重新发布,但务必保留文章署名吕毅(包含链接:http://blog.csdn.net/wpwalter/),不得用于商业目的,基于本文修改后的作品务必以相同的许可发布。
1175 0