Pagini recente » Cod sursa (job #1176652) | Cod sursa (job #2043338) | Cod sursa (job #2223092) | Cod sursa (job #787590) | Cod sursa (job #40466)
Cod sursa(job #40466)
#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<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();
}