C3 cheat sheet for data mining

test.cpp

// fuck this man !!
 
#include<bits/stdc++.h> 
#include <iostream> 
#include <vector> 
#include <iterator>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define f(i,x,n) for(int i=x;i<(int)n;++i)
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvvi vector<vector<vector<int>>>
#define pq priority_queue<int>
#define pqs priority_queue<int,vi,greater<int>>	
#define vpii vector<pair<int,int>>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define mpi map<int,int>
#define lb lower_bound //lower_bound returns an iterator pointing to the first element in the range [first,last) which has a value not less than ‘val’. 
#define ub upper_bound // upper_bound returns an iterator pointing to the first element ian the range [first,last) which has a value greater than ‘val’. 
 
 
int mod=1e9+7;
const int mxn=210000;


void least_regression(){
	ld x[10],y[10];
	int n=5;
	f(i,0,n) cin>>x[i]>>y[i];
	ld x_mean=0; f(i,0,n) x_mean+=x[i]; x_mean/=n;
	ld y_mean=0; f(i,0,n) y_mean+=y[i]; y_mean/=n;
	cout<<x_mean<<" "<<y_mean<<endl;
	ld num=0; f(i,0,n) num+=(x[i]-x_mean)*(y[i]-y_mean);
	ld den=0; f(i,0,n) den+=(x[i]-x_mean)*(x[i]-x_mean);
	ld m=num/den;
	ld c=((y_mean)-(m*x_mean));
	cout<<m<<" "<<c<<endl;
}

ld manhatten(ld x1,ld y1,ld x2,ld y2){
	return abs(x1-x2)+abs(y1-y2);
}

ld eucl(ld x1,ld y1,ld x2,ld y2){
	x1-=x2; y1-=y2;
	x1*=x1; y1*=y1;
	x1+=y1;
	return sqrt(x1);
}


void dbscan(){
	int n; cin>>n;
	ld x[n],y[n]; f(i,0,n) cin>>x[i]>>y[i];
	int curr_class=1;
	int assigned_class[n];
	f(i,0,n) assigned_class[i]=-1;
	bool core_point[n]={0};
	bool border_point[n]={0};
	bool noise_point[n]={0};
	ld eps=2.5; int mnp=3;
	f(i,0,n){
		vi here;
		f(j,0,n) if(eucl(x[i],y[i],x[j],y[j])<=eps) here.pb(j); 
		for(auto it : here){
			cout<<it+1<<" ";
			cout<<eucl(x[i],y[i],x[it],y[it])<<endl;
		}
		cout<<endl;
		if(sz(here)>mnp){
			core_point[i]=1;
			int num=-1;
			for(auto it : here) if(assigned_class[it]!=-1) {num=assigned_class[it]; break;}
			if(num==-1){assigned_class[i]=curr_class; curr_class++;}
			else assigned_class[i]=num;
		}
	}
	f(i,0,n) {
		if(core_point[i]) continue;
		vi here;
		f(j,0,n) if(eucl(x[i],y[i],x[j],y[j])<=eps) here.pb(j);
		bool go=0; for(auto it : here) if(core_point[it]==true) go=1;
		if(go){
			border_point[i]=true;
			int num=-1;
			for(auto it : here) if(assigned_class[it]!=-1) {num=assigned_class[it]; break;}
			if(num==-1){assigned_class[i]=curr_class; curr_class++;}
			else assigned_class[i]=num;	
		}else noise_point[i]=true;
	}
	f(i,0,n){
		if(core_point[i]) 
			cout<<"core_point "<<assigned_class[i]<<"\n";
		else if(border_point[i])
			cout<<"border_point "<<assigned_class[i]<<"\n";
		else cout<<"noise_point\n";
	}
}

void single_hierarichal_clustering(){
	int n; cin>>n;
	vector<vector<ld>> vt(n,vector<ld>(n));
	f(i,0,n) f(j,0,n) cin>>vt[i][j];
	vvi cluster; f(i,0,n){
		vi here; here.pb(i); cluster.pb(here);
	}
	while(sz(cluster)!=1){
		int now=sz(cluster);
		vector<vector<ld>> dis(now,vector<ld>(now));
		f(i,0,now){
			f(j,0,now){
				ld mn=1e18;
				for(auto it1 : cluster[i]) for(auto it2 : cluster[j]) mn=min(mn,vt[it1][it2]);
				dis[i][j]=mn;
			}
		}
		cout<<"Clusters now --------------------------\n";
		for(auto it : cluster){ cout<<"[";
			for(auto ip : it ) cout<<ip<<" ";
			cout<<"]\n";
		}
		cout<<"Distance matix ------------------------\n";
		f(i,0,now){
			f(j,0,now)
				cout<<dis[i][j]<<" ";
			cout<<"\n";
		}
		ld mn=1e18; int go1=-1,go2=-1;
		f(i,0,now) f(j,i+1,now) {
			if(dis[i][j]<mn) {
				mn=dis[i][j];
				go1=i; go2=j;
			}
		}
		assert(go1!=-1); assert(go2!=-1);
		cout<<"Combining Clusters-------------------\n";
		cout<<"["; for(auto it : cluster[go1]) cout<<it<<" "; cout<<"]\n";
		cout<<"["; for(auto it : cluster[go2]) cout<<it<<" "; cout<<"]\n";
		cout<<"Distance between combined Clusters----\n";
		cout<<mn<<"\n";
		vvi new_cluster;
		f(i,0,now){
			if(i==go1 || i==go2) continue;
			new_cluster.pb(cluster[i]);
		}
		vi helper; for(auto it : cluster[go1]) helper.pb(it);
		for(auto it : cluster[go2]) helper.pb(it);
		new_cluster.pb(helper);
		cluster=new_cluster;
	}
}

void complete_hierarichal_clustering(){
	int n; cin>>n;
	vector<vector<ld>> vt(n,vector<ld>(n));
	f(i,0,n) f(j,0,n) cin>>vt[i][j];
	vvi cluster; f(i,0,n){
		vi here; here.pb(i); cluster.pb(here);
	}
	while(sz(cluster)!=1){
		int now=sz(cluster);
		vector<vector<ld>> dis(now,vector<ld>(now));
		f(i,0,now){
			f(j,0,now){
				ld mn=-1e18;
				for(auto it1 : cluster[i]) for(auto it2 : cluster[j]) mn=max(mn,vt[it1][it2]);
				dis[i][j]=mn;
			}
		}
		cout<<"Clusters now --------------------------\n";
		for(auto it : cluster){ cout<<"[";
			for(auto ip : it ) cout<<ip<<" ";
			cout<<"]\n";
		}
		cout<<"Distance matix ------------------------\n";
		f(i,0,now){
			f(j,0,now)
				cout<<dis[i][j]<<" ";
			cout<<"\n";
		}
		ld mn=1e18; int go1=-1,go2=-1;
		f(i,0,now) f(j,i+1,now) {
			if(dis[i][j]<mn) {
				mn=dis[i][j];
				go1=i; go2=j;
			}
		}
		assert(go1!=-1); assert(go2!=-1);
		cout<<"Combining Clusters-------------------\n";
		cout<<"["; for(auto it : cluster[go1]) cout<<it<<" "; cout<<"]\n";
		cout<<"["; for(auto it : cluster[go2]) cout<<it<<" "; cout<<"]\n";
		cout<<"Distance between combined Clusters----\n";
		cout<<mn<<"\n";
		vvi new_cluster;
		f(i,0,now){
			if(i==go1 || i==go2) continue;
			new_cluster.pb(cluster[i]);
		}
		vi helper; for(auto it : cluster[go1]) helper.pb(it);
		for(auto it : cluster[go2]) helper.pb(it);
		new_cluster.pb(helper);
		cluster=new_cluster;
	}
}

void average_hierarichal_clustering(){
	int n; cin>>n;
	vector<vector<ld>> vt(n,vector<ld>(n));
	f(i,0,n) f(j,0,n) cin>>vt[i][j];
	vvi cluster; f(i,0,n){
		vi here; here.pb(i); cluster.pb(here);
	}
	while(sz(cluster)!=1){
		int now=sz(cluster);
		vector<vector<ld>> dis(now,vector<ld>(now));
		f(i,0,now){
			f(j,0,now){
				ld mn=0;
				for(auto it1 : cluster[i]) for(auto it2 : cluster[j]) mn+=vt[it1][it2];
				mn/=(sz(cluster[i])*sz(cluster[j]));
				dis[i][j]=mn;
			}
		}
		cout<<"Clusters now --------------------------\n";
		for(auto it : cluster){ cout<<"[";
			for(auto ip : it ) cout<<ip<<" ";
			cout<<"]\n";
		}
		cout<<"Distance matix ------------------------\n";
		f(i,0,now){
			f(j,0,now)
				cout<<dis[i][j]<<" ";
			cout<<"\n";
		}
		ld mn=1e18; int go1=-1,go2=-1;
		f(i,0,now) f(j,i+1,now) {
			if(dis[i][j]<mn) {
				mn=dis[i][j];
				go1=i; go2=j;
			}
		}
		assert(go1!=-1); assert(go2!=-1);
		cout<<"Combining Clusters-------------------\n";
		cout<<"["; for(auto it : cluster[go1]) cout<<it<<" "; cout<<"]\n";
		cout<<"["; for(auto it : cluster[go2]) cout<<it<<" "; cout<<"]\n";
		cout<<"Distance between combined Clusters----\n";
		cout<<mn<<"\n";
		vvi new_cluster;
		f(i,0,now){
			if(i==go1 || i==go2) continue;
			new_cluster.pb(cluster[i]);
		}
		vi helper; for(auto it : cluster[go1]) helper.pb(it);
		for(auto it : cluster[go2]) helper.pb(it);
		new_cluster.pb(helper);
		cluster=new_cluster;
	}
}


void solve(){
	ld x[8], y[8];
	f(i,0,8) cin>>x[i]>>y[i];
	f(i,0,8){
		cout<<eucl(x[i],y[i],7.00,13.00/3.00)<<endl;
	}
}
 
int32_t main(){
 	ios_base::sync_with_stdio(false);cin.tie(NULL);	
	srand(time(0)); 	
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	int t=1; //cin>>t;
	while(t--) complete_hierarichal_clustering();
	return 0;
}