Pagini recente » Clasament testeaza | Cod sursa (job #1327615) | Cod sursa (job #2408854) | Cod sursa (job #1778121) | Cod sursa (job #2569449)
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin("desen.in");
ofstream fout("desen.out");
const int INF = 1<<25;
struct punct{
int x,y;
}p[1009];
int m[1005],sz[1005];
struct segment{
int x,y;
double d;
}a[100008];
vector<segment> A;
double dist(punct A, punct B)
{
return sqrt( (A.x-B.x)*(A.x-B.x) + (A.y - B.y) * (A.y-B.y) );
}
int N;
bool comp(segment A, segment B)
{
return A.d < B.d;
}
int Find(int val)
{
int root = val;
while(root!= m[root])
root = m[root];
while(m[val] != root)
{
int aux = m[val];
m[val] = root;
val = aux;
}
return root;
}
void Union(int X, int Y)
{
int rootx = Find(X);
int rooty = Find(Y);
if(sz[rootx] > sz[rooty])
{
sz[rootx] += sz[rooty];
m[rooty] = rootx;
}
else
{
sz[rooty] += sz[rootx];
m[rootx] = rooty;
}
}
void Do()
{
int i,j;
int w,z;
double c;
double total = 0;
vector<segment>Aux;
sort(A.begin(), A.end(), comp);
for(i = 0; i<A.size(); ++i)
{
w = A[i].x;
z = A[i].y;
c = A[i].d;
if(Find(w) != Find(z))
{
total += c;
Union(w,z);
Aux.push_back(A[i]);
}
}
A.erase(A.begin(), A.end());
for( i = 0; i<Aux.size(); ++i)
A.push_back(Aux[i]);
fout<<fixed<<setprecision(6)<<total<<"\n";
}
void Read()
{
int i,j;
double c;
segment aux;
fin>>N;
for(i = 1; i<=N; ++i)
{
fin>>p[i].x>>p[i].y;
for(j = 1; j <=i; ++j)
{
m[j] = j;
sz[j] = 1;
}
for(j = 1; j < i; ++j)
{
c = dist(p[i], p[j]);
aux.x = i;
aux.y = j;
aux.d = c;
A.push_back(aux);
}
Do();
}
}
int main()
{
Read();
return 0;
}