Cod sursa(job #1850246)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 18 ianuarie 2017 13:15:53
Problema Adapost Scor 7
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#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);
}