时间限制:
1000ms
内存限制:
65536kB
描述
有N(N <= 1000)个网页,
<wbr>我们想按照它们的相似度或差异度,把它们聚成K(2 <= K <= <wbr>N)个类。每个网页都具有一些属性,<wbr>简单起见我们认为每个网页只有三个属性:x、y、z。<wbr>归一化之后,这三个属性的取值范围都是[0,1]。两个网页i、<wbr>j的差异度如下定义:s(i,j) = (x_j-x_i)^2 + (y_j-y_i)^2 + (z_j-z_i)^2。请求出最大的t,<wbr>每个类至少包含一个网页,并且其中任意两个位于不同类中的网页的差异度都至少为t。</wbr></wbr></wbr></wbr></wbr></wbr>
输入
第一行包含两个整数N和K,后面N行每行三个实数,分别为x、y、z
输出
最大的t的值,使用四舍五入在小数点后保留六位小数。
样例输入
5 30.1 0.2 0.40.2 0.8 0.70.3 0.4 0.50.0 0.5 0.00.3 0.3 0.2
样例输出
0.170000
#include <iostream>
#include <cmath>
#include "stdio.h"
int N,K=3;
float a[1000][3];
float difference(int i,int j)
{
float sum=0;
for(int k=0;k<K;++k)
sum+=pow(a[i][k]-a[j][k],2);
return sum;
}
float abss(float a)
{
if(a> 0)
return a;
else
return -a;
}
int dif(int i,int j,float M)
{
for(int k=0;k<K;++k)
{
if(abss(a[i][k]-a[j][k]) < M)
return 0;
}
return 1;
}
int main()
{
int i,j;
float data;
scanf("%d",&N);
scanf("%d",&K);
float b[5][3]={
{0.1,0.2,0.4},{0.2,0.8,0.7},{0.3,0.4,0.5},{0.0,0.5,0.0},{0.3,0.3,0.2}
};
for(i=0;i<N;++i)
{
for(j=0;j<K;++j)
{
scanf("%f",&data);
a[i][j]=data;
}
}
float min=1;
for(i=0;i<N;++i)
{
for(j=i+1;j<N;++j)
{
if(dif(i,j,difference(i,j)))
{
min=difference(i,j);
}
}
}
printf("%.6f",min);
return 0;
}
分享到:
相关推荐
第二类是车辆的市场属性(如车辆名称、车辆价格、风险评估等级)。 26个字段主要分为数值型变量和类别型变量两类。 第二步:原始数据描述性统计及变量分布可视化 对原始数据进行描述性统计并对数据中的字段分布进行...
阿里云-天池数据分析竞赛:汽车产品聚类分析.zip
商务数据分析与统计建模:chap5 聚类分析.ppt
推荐引擎算法学习导论:协同过滤、聚类、分类.docx推荐引擎算法学习导论:协同过滤、聚类、分类.docx推荐引擎算法学习导论:协同过滤、聚类、分类.docx推荐引擎算法学习导论:协同过滤、聚类、分类.docx推荐引擎算法...
资产配置定量研究系列之十一:利用层次聚类法,构建更具风险分散能力的QDII基金配置方法
20201217-光大证券-资产配置定量研究系列之十一:利用层次聚类法,构建更具风险分散能力的QDII基金配置方法.pdf
dm-家庭作业3 基于马尔可夫聚类算法的复杂网络聚类分析
2. 对于有分类真实结果做对照的,则可以使用真实标签与预测标签的相似、重复、完整性等度量计算,但是需要注意的是,聚类结果的标签值与其真实类别的标签值没有关系,结果只关注数据点是否属于同一类; 3. 业务类的...
毕业设计:基于C++的AP聚类算法设计与实现 毕业设计:基于C++的AP聚类算法设计与实现 毕业设计:基于C++的AP聚类算法设计与实现 毕业设计:基于C++的AP聚类算法设计与实现 毕业设计:基于C++的AP聚类算法设计与实现 ...
MYDBSCAN:基于密度的聚类DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法的底层实现 MYAP:基于划分的聚类AP(Affinity Propagation Clustering Algorithm )算法的底层实现--近邻传播...
2.6:聚类分析—层次聚类法.do
2.5.1:聚类分析—快速聚类法.do
名称:AP聚类算法 功能:聚类数据集 类别:新聚类算法
名称:DPC聚类算法 功能:聚类数据集 类别:密度聚类算法
LWMC:用于集成聚类的局部加权元聚类算法
ziclust:零膨胀聚类的混合模型
然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足: %同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行计算的。 ...
名称:DBSCAN经典聚类算法 功能:聚类数据集 类别:密度聚类算法