#include<bits/stdc++.h>
using namespace std;
int main()
{
float mid(set <float> s);
float dist,dist2,mid1,mid2;
set <float> data;
data.insert(2);
data.insert(4);
data.insert(10);
data.insert(12);
data.insert(3);
data.insert(20);
data.insert(30);
data.insert(11);
data.insert(25);
set <float> :: iterator itr;
cout << "Data = {";
for (itr = data.begin(); itr != data.end(); ++itr)
{
cout<< *itr<<" ";
}
cout <<"}"<<endl;
set<float> cluster1;
set<float>cluster2;
set<float> pre_cluster1;
set<float>pre_cluster2;
cout<<"choose two random median from data: ";
cin>>mid1>>mid2;
while(1)
{
for (itr = data.begin(); itr != data.end(); ++itr)
{
dist = abs(mid1 - *itr);
dist2 = abs(mid2 - *itr);
if(dist<dist2)
{
cluster1.insert(*itr);
cluster2.erase(*itr);
}
else
{
cluster2.insert(*itr);
cluster1.erase(*itr);
}
}
cout << "k1 = {";
for (itr = cluster1.begin(); itr != cluster1.end(); ++itr)
{
cout<< *itr<<" ";
}
cout <<"}";
cout << " k2 = {";
for (itr = cluster2.begin(); itr != cluster2.end(); ++itr)
{
cout<< *itr <<" ";
}
mid1 = mid(cluster1);
mid2 = mid(cluster2);
cout<<"} m1: "<<mid1<<" m2: "<<mid2<<endl;
// cout<<"Mids : "<<mid1<<ends<<mid2<<endl;
if((cluster1 == pre_cluster1) && (cluster2 == pre_cluster2) )
break;
pre_cluster1 = cluster1;
pre_cluster2 = cluster2;
}
cout << endl;
cout << "\nThe first cluster k1 is : ";
for (itr = pre_cluster1.begin(); itr != pre_cluster1.end(); ++itr)
{
cout<<'\t'<< *itr;
}
cout << endl;
cout << endl;
cout << "\nThe second cluster k2 is : ";
for (itr = cluster2.begin(); itr != cluster2.end(); ++itr)
{
cout<<'\t'<< *itr;
}
cout << endl;
return 0;
}
float mid(set <float> s)
{
float sum =0;
set <float> :: iterator itr;
for (itr = s.begin(); itr != s.end(); ++itr)
{
sum += *itr;
}
return sum/s.size();
}
CiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgoKCmludCBtYWluKCkKewogICAgZmxvYXQgbWlkKHNldCA8ZmxvYXQ+IHMpOwogICAgZmxvYXQgZGlzdCxkaXN0MixtaWQxLG1pZDI7CiAgICBzZXQgPGZsb2F0PiBkYXRhOwoKICAgIGRhdGEuaW5zZXJ0KDIpOwogICAgZGF0YS5pbnNlcnQoNCk7CiAgICBkYXRhLmluc2VydCgxMCk7CiAgICBkYXRhLmluc2VydCgxMik7CiAgICBkYXRhLmluc2VydCgzKTsKICAgIGRhdGEuaW5zZXJ0KDIwKTsKICAgIGRhdGEuaW5zZXJ0KDMwKTsKICAgIGRhdGEuaW5zZXJ0KDExKTsKICAgIGRhdGEuaW5zZXJ0KDI1KTsKCiAgICBzZXQgIDxmbG9hdD4gIDo6IGl0ZXJhdG9yIGl0cjsKCiAgICAgICAgICAgIGNvdXQgPDwgIkRhdGEgPSB7IjsKICAgICAgICBmb3IgKGl0ciA9IGRhdGEuYmVnaW4oKTsgaXRyICE9IGRhdGEuZW5kKCk7ICsraXRyKQogICAgICAgIHsKICAgICAgICAgICAgY291dDw8ICppdHI8PCIgIjsKCiAgICAgICAgfQoKICAgICAgICBjb3V0IDw8In0iPDxlbmRsOwoKICAgIHNldDxmbG9hdD4gY2x1c3RlcjE7CiAgICBzZXQ8ZmxvYXQ+Y2x1c3RlcjI7CiAgICBzZXQ8ZmxvYXQ+IHByZV9jbHVzdGVyMTsKICAgIHNldDxmbG9hdD5wcmVfY2x1c3RlcjI7CiAgICBjb3V0PDwiY2hvb3NlIHR3byByYW5kb20gbWVkaWFuIGZyb20gZGF0YTogIjsKICAgIGNpbj4+bWlkMT4+bWlkMjsKCgoKCgogICAgd2hpbGUoMSkKICAgIHsKCiAgICAgICAgZm9yIChpdHIgPSBkYXRhLmJlZ2luKCk7IGl0ciAhPSBkYXRhLmVuZCgpOyArK2l0cikKICAgICAgICB7CiAgICAgICAgICAgIGRpc3QgPSBhYnMobWlkMSAtICppdHIpOwogICAgICAgICAgICBkaXN0MiA9IGFicyhtaWQyIC0gKml0cik7CgogICAgICAgICAgICBpZihkaXN0PGRpc3QyKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBjbHVzdGVyMS5pbnNlcnQoKml0cik7CiAgICAgICAgICAgICAgICBjbHVzdGVyMi5lcmFzZSgqaXRyKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGNsdXN0ZXIyLmluc2VydCgqaXRyKTsKICAgICAgICAgICAgICAgIGNsdXN0ZXIxLmVyYXNlKCppdHIpOwogICAgICAgICAgICB9CgogICAgICAgIH0KICAgICAgICBjb3V0IDw8ICJrMSA9IHsiOwogICAgICAgIGZvciAoaXRyID0gY2x1c3RlcjEuYmVnaW4oKTsgaXRyICE9IGNsdXN0ZXIxLmVuZCgpOyArK2l0cikKICAgICAgICB7CiAgICAgICAgICAgIGNvdXQ8PCAqaXRyPDwiICI7CgogICAgICAgIH0KCiAgICAgICAgY291dCA8PCJ9IjsKICAgICAgICBjb3V0IDw8ICIgIGsyID0geyI7CiAgICAgICAgZm9yIChpdHIgPSBjbHVzdGVyMi5iZWdpbigpOyBpdHIgIT0gY2x1c3RlcjIuZW5kKCk7ICsraXRyKQogICAgICAgIHsKICAgICAgICAgICAgY291dDw8ICppdHIgPDwiICI7CgogICAgICAgIH0KCgoKCiAgICAgICAgbWlkMSA9IG1pZChjbHVzdGVyMSk7CiAgICAgICAgbWlkMiA9IG1pZChjbHVzdGVyMik7Cgpjb3V0PDwifSAgbTE6ICI8PG1pZDE8PCIgIG0yOiAiPDxtaWQyPDxlbmRsOwoKCgogICAgICAgIC8vIGNvdXQ8PCJNaWRzIDogIjw8bWlkMTw8ZW5kczw8bWlkMjw8ZW5kbDsKCiAgICAgICAgaWYoKGNsdXN0ZXIxID09IHByZV9jbHVzdGVyMSkgJiYgKGNsdXN0ZXIyID09IHByZV9jbHVzdGVyMikgKQogICAgICAgICAgICBicmVhazsKCiAgICAgICAgcHJlX2NsdXN0ZXIxID0gY2x1c3RlcjE7CiAgICAgICAgcHJlX2NsdXN0ZXIyID0gY2x1c3RlcjI7CiAgICB9CgoKCgogICAgY291dCA8PCBlbmRsOwoKICAgIGNvdXQgPDwgIlxuVGhlIGZpcnN0IGNsdXN0ZXIgazEgaXMgOiAiOwogICAgZm9yIChpdHIgPSBwcmVfY2x1c3RlcjEuYmVnaW4oKTsgaXRyICE9IHByZV9jbHVzdGVyMS5lbmQoKTsgKytpdHIpCiAgICB7CiAgICAgICAgY291dDw8J1x0Jzw8ICppdHI7CgogICAgfQoKICAgIGNvdXQgPDwgZW5kbDsKCiAgICBjb3V0IDw8IGVuZGw7CgogICAgY291dCA8PCAiXG5UaGUgc2Vjb25kIGNsdXN0ZXIgazIgaXMgOiAiOwogICAgZm9yIChpdHIgPSBjbHVzdGVyMi5iZWdpbigpOyBpdHIgIT0gY2x1c3RlcjIuZW5kKCk7ICsraXRyKQogICAgewogICAgICAgIGNvdXQ8PCdcdCc8PCAqaXRyOwoKICAgIH0KCiAgICBjb3V0IDw8IGVuZGw7CgoKCiAgICByZXR1cm4gMDsKfQoKCmZsb2F0IG1pZChzZXQgPGZsb2F0PiBzKQp7CgogICAgZmxvYXQgc3VtID0wOwogICAgc2V0ICA8ZmxvYXQ+ICA6OiBpdGVyYXRvciBpdHI7CgogICAgZm9yIChpdHIgPSBzLmJlZ2luKCk7IGl0ciAhPSBzLmVuZCgpOyArK2l0cikKICAgIHsKICAgICAgICBzdW0gKz0gKml0cjsKCiAgICB9CgogICAgcmV0dXJuIHN1bS9zLnNpemUoKTsKfQoKCg==