Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #2810511) | Cod sursa (job #1391526) | Cod sursa (job #689857)
Cod sursa(job #689857)
#include <fstream>
#include <iomanip>
#include <math.h>
#define NMAx 4120
#define EPS 0.000000001
#define oo (1<<30)
#define min(a,b) ((a)<(b)?(a):(b))
#define pp(a) ((a)*(a))
#define dist(i,j) sqrt((pp(X[i]-X[j])+pp(Y[i]-Y[j])))
#define father(nod) (nod/2)
#define left(nod) (2*nod)
#define right(nod) (2*nod+1)
#define cmp(a,b) (APM[Heap[a]]+EPS<APM[Heap[b]])
using namespace std;
int vf,loc[NMAx],Heap[NMAx];
int n,m;
double X[NMAx],Y[NMAx];
double S,APM[NMAx];
void up(int nod) {
while(nod>1&&cmp(nod,father(nod))) {
swap(Heap[nod],Heap[father(nod)]);
swap(loc[Heap[nod]],loc[Heap[father(nod)]]);
nod=father(nod);
}
}
void down(int nod) {
int son;
do {son=0;
if(left(nod)<=vf) {
son=left(nod);
if(right(nod)<=vf&&cmp(right(nod),son))
son=right(nod);
if(cmp(nod,son))
son=0;
}
if(son) {
swap(Heap[nod],Heap[son]);
swap(loc[Heap[nod]],loc[Heap[son]]);
nod=son;
}
}while(son);
}
void init_APM() {
int i,j;
double e;
//include_APM(0)
for(i=n+1;i<=n+m;i++) {
e=oo;
for(j=1;j<=n;j++)
e=min(e,dist(i,j));
APM[i]=e;
Heap[++vf]=i;
loc[i]=vf;
up(loc[i]);
}
}
void include_APM(int nod) {
int i;
for(i=n+1;i<=n+m;i++)
if(APM[i]>dist(nod,i)+EPS&&loc[i]) {
APM[i]=dist(nod,i);
up(loc[i]);
}
}
int radacina_Heap() {
int nod=Heap[1];
Heap[1]=Heap[vf];
loc[Heap[1]]=1;
loc[nod]=0;
down(1);
return nod;
}
void citire() {
ifstream in("retea2.in");
in>>n>>m;
for(int i=1;i<=n+m;i++)
in>>X[i]>>Y[i];
in.close();
}
int main() {
int nod,i;
citire();
init_APM();
for(i=1;i<=m;i++) {
nod=radacina_Heap();
S+=APM[nod];
include_APM(nod);
}
ofstream out("retea2.out");
out<<fixed<<setprecision(9)<<S<<'\n';
out.close();
return 0;
}