Pagini recente » Cod sursa (job #222804) | Cod sursa (job #1566481) | Cod sursa (job #1223287) | Cod sursa (job #319120) | Cod sursa (job #1850246)
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct str2
{
double v;
int p;
};
struct str
{
str2 st[401];
double y;
double x;
int stp;
} sld[401];
int n;
double y,x,res,sum;
int heap[401],l;
bool ap[401];
bool comp(const str2 &a,const str2 &b)
{
return a.v<b.v;
}
void upheap(int nod)
{
if(nod!=1)
{
if(sld[heap[nod]].st[sld[heap[nod]].stp].v>sld[heap[nod/2]].st[sld[heap[nod/2]].stp].v)
{
swap(heap[nod],heap[nod/2]);
upheap(nod/2);
}
}
}
void downheap(int nod)
{
if(nod*2<l)
{
if(sld[heap[nod]].st[sld[heap[nod]].stp].v<sld[heap[nod*2]].st[sld[heap[nod*2]].stp].v)
{
if(sld[heap[nod*2+1]].st[sld[heap[nod*2+1]].stp].v<sld[heap[nod*2]].st[sld[heap[nod*2]].stp].v)
{
swap(heap[nod],heap[nod*2]);
downheap(nod*2);
}
else
{
swap(heap[nod],heap[nod*2+1]);
downheap(nod*2+1);
}
}
else if(sld[heap[nod]].st[sld[heap[nod]].stp].v<sld[heap[nod*2+1]].st[sld[heap[nod*2+1]].stp].v)
{
swap(heap[nod],heap[nod*2+1]);
downheap(nod*2+1);
}
}
else if(nod*2==l)
{
if(sld[heap[nod]].st[sld[heap[nod]].stp].v>sld[heap[nod*2]].st[sld[heap[nod*2]].stp].v)
{
swap(heap[nod],heap[nod*2]);
downheap(nod*2);
}
}
}
int main()
{
freopen("adapost.in","r",stdin);
freopen("adapost.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf %lf",&sld[i].y,&sld[i].x);
sld[i].stp=1;
}
for(int i=1;i<=n;i++)
{
scanf("%lf %lf",&y,&x);
for(int j=1;j<=n;j++)
{
sld[j].st[i].v=sqrt((sld[j].y-y)*(sld[j].y-y)+(sld[j].x-x)*(sld[j].x-x));
sld[j].st[i].p=i;
}
}
for(int i=1;i<=n;i++)
{
sort(sld[i].st+1,sld[i].st+n+1,comp);
}
for(int i=1;i<=n;i++)
{
l++;
heap[l]=i;
upheap(i);
}
res=sld[heap[1]].st[1].v;
while(l!=0)
{
sum+=sld[heap[1]].st[sld[heap[1]].stp].v;
ap[sld[heap[1]].st[sld[heap[1]].stp].p]=1;
swap(heap[1],heap[l]);
l--;
for(int i=1;i<=l;i++)
{
while(ap[sld[heap[i]].st[sld[heap[i]].stp].p]==1)
{
sld[heap[i]].stp++;
}
}
downheap(1);
}
printf("%lf %lf",res,sum);
}