2021-10-06 组队赛——2019-icpc-Seoul-题解

题意：
给你三维平面上的 n < = 100 n<=100 n<=100个点，将他们最多分成 k < = 2 k<=2 k<=2类。每一类的价值是，
要求使所有类的价值和 最小，输出最小值。任意三点不共线，任意四点不共面。

思路一：
这个价值函数类似于方差，就是要让分出的类，尽可能地聚合。

考虑用K-means算法。
1）考虑先随机k个聚合点，
2) 然后每次把其他点，归属到距离最近的聚合点
3) 把每个聚合点调整到 属于他的那个点集最靠近质心的点
重复 第 2、3 步，最后剩下的聚合点就是使得每个集合 尽可能聚合的中心点。

代码：

#include
using namespace std;
const double eps=1e-10;

int n,k;
struct node{
	double x,y,z;
}z[105];
double dis(double x1,double x2,double y1,double y2,double z1,double z2){
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2);
}
vectormp[2];
int main(){
	cin>>n>>k;
	cout<>z[i].x>>z[i].y>>z[i].z;
	}
	double ans=0;
	if(n==1){
		cout<<1e-12< 
思路二：
 考虑利用任意四点不共面的性质，我们用
    
     
      
       
        
         n
        
        
         3
        
       
      
      
       n^3
      
     
    n3的复杂度枚举每个面，然后这个面就把点集分成了两个部分，最后我们再二进制枚举面上的三个点所属哪个面就等于枚举了所有情况，然后对答案取min。
 
代码：