Cod sursa(job #40514)

Utilizator thestickTudor A thestick Data 27 martie 2007 14:37:45
Problema Adapost Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct{double x,y;} punct;
punct ad[401],so[401];
int sol[401],nou[401],big[401];
long n;

double dstdp(punct a,punct b)
{
return(sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}

void cit()
{
FILE *f=fopen("adapost.in","r");
long i;
fscanf(f,"%d",&n);

for(i=0;i<n;i++)fscanf(f,"%lf %lf",&so[i].x,&so[i].y);

for(i=0;i<n;i++)fscanf(f,"%lf %lf",&ad[i].x,&ad[i].y);
}

double getmin(int v[])
{
long i;
double dm=0,ge;
for(i=0;i<n;i++){ge=dstdp(so[i],ad[v[i]]);if(dm<ge)dm=ge;}return dm;
}

int getpmin(int v[])
{
long i,pm;
double dm=0,ge;
for(i=0;i<n;i++)
{
ge=dstdp(so[i],ad[v[i]]);
if(dm<ge){dm=ge;pm=i;}
}
return pm;
}


double sdist(int v[])
{
long i;
double s=0;

for(i=0;i<n;i++)
s=s+dstdp(so[i],ad[v[i]]);
return s;
}


int prob(int a[],int b[])
{
if(getmin(a)>getmin(b))return 100;
return 20;
}

void rez()
{
long i,j,p,q;

long temp;

for(i=0;i<n;i++)sol[i]=i;
for(i=0;i<n;i++)big[i]=i;

double g=sdist(sol);

temp=10*n;

while(temp>0)
{

for(i=0;i<n;i++)nou[i]=sol[i];

for(j=0;j<2*n;j++)
{
        for(i=0;i<temp;i++)
        {
        p=q=1;
        while(p==q)
        {
        p=random()%n;
        q=random()%n;
        }
        nou[p]=nou[p]^nou[q];
        nou[q]=nou[p]^nou[q];
        nou[p]=nou[p]^nou[q];
        }

        if(getmin(nou)==getmin(big))
            if(sdist(nou)<sdist(big))
                for(i=0;i<n;i++)big[i]=nou[i];


        if(getmin(nou)<getmin(big))
                for(i=0;i<n;i++)big[i]=nou[i];


        if(prob(sol,nou)>random()%100)
                {
                for(i=0;i<n;i++)sol[i]=nou[i];
                }
        fprintf(stderr,"%d s=%lf n=%lf b=%lf ss=%lf sn=%lf sb=%lf\n",temp,getmin(sol),getmin(nou),getmin(big),sdist(sol),sdist(nou),sdist(big));
}
temp--;
}

}


void scr()
{
FILE *f=fopen("adapost.out","w");
fprintf(f,"%.4lf %.4lf",getmin(big),sdist(big));
fclose(f);
}

int main()
{
srand(time(0));
cit();
rez();
scr();
}