Cod sursa(job #40371)

Utilizator thestickTudor A thestick Data 27 martie 2007 13:32:50
Problema Adapost Scor 2
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 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 prob(int a[],int b[])
{
if(getmin(a)>getmin(b))return 80;
return 10;
}

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;


temp=4*n;

while(temp>0)
{

for(j=0;j<2*n;j++)
{
        for(i=0;i<n;i++)nou[i]=sol[i];

        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))
                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];
                }
        }
temp=(temp*9999)/10000;
}

}

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

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

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();
}