Cod sursa(job #196797)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 29 iunie 2008 08:41:35
Problema Adapost 2 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include<stdio.h>
#include<math.h>

#define NMAX 50001
struct pct{double x,y;};
struct cmapct{pct p;int nr;double sd;};
pct v[NMAX];
cmapct w[NMAX];
double d[NMAX];
int n,nrpa;

double dist(double x,double y){
int i;
double rez=0.0,patr,rad,term;
for(i=0;i<n;++i){
	patr=(x-v[i].x)*(x-v[i].x)+(y-v[i].y)*(y-v[i].y);
	if(patr<0) patr=-patr;
	rad=sqrt(patr);
	term=rad;
	rez+=term;
	}
return rez;
}

void f(double x,double y,double &fx,double &fy){
int i;
double patr,rad,term1,term2;
fx=fy=0;
for(i=0;i<n;++i){
	patr=(x-v[i].x)*(x-v[i].x)+(y-v[i].y)*(y-v[i].y);
	if(patr<0) patr=-patr;
	rad=sqrt(patr);
	if(rad){
		term1=(x-v[i].x)/rad;
		term2=(y-v[i].y)/rad;
		}
	else term1=term2=0.0;
	fx+=term1;fy+=term2;
	}
}

void poz(int li,int ls,int &piv){
int i=li,j=ls,d=0;
cmapct t;
while(i<j){
	if(w[i].sd>w[j].sd){
		t=w[i];w[i]=w[j];w[j]=t;d=1-d;
		}
	i+=d;j-=1-d;
	}
piv=i;
}
void qsrt(int st,int dr){
int piv;
if(st<dr){
	poz(st,dr,piv);
	qsrt(st,piv-1);
	qsrt(piv+1,dr);
	}
}

int main(){
FILE *f=fopen("adapost2.in","r");
freopen("adapost2.out","w",stdout);
fscanf(f,"%d",&n);
double sx=0.0,sy=0.0,xmed,ymed,sdmed;
double xi,xs,yi,ys,x0,y0,ex,ey,xmij,ymij,mx,my,xmax,ymax,xmin,ymin;
ex=ey=0.0001;
int i;
xmax=ymax=0.0;
xmin=ymin=10000.0;
for(i=0;i<n;++i){
	fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
	sx+=v[i].x;
	sy+=v[i].y;
	if(xmax<v[i].x) xmax=v[i].x;
	if(ymax<v[i].y) ymax=v[i].y;
	if(xmin>v[i].x) xmin=v[i].x;
	if(ymin>v[i].y) ymin=v[i].y;
	}
xmed=sx/n;ymed=sy/n;
xi=xmed;yi=ymed;
sdmed=dist(xi,yi);
double fx,fy,dmin,dxmax,dymax,k=0.2;
dxmax=xmax-xmin;
dymax=ymax-ymin;
dmin=dxmax>dymax?dxmax:dymax;
dmin*=k;
for(i=0;i<n;++i)
	if(v[i].x>=xmed-dmin&&v[i].x<=xmed+dmin&&
	   v[i].y>=ymed-dmin&&v[i].y<=ymed+dmin){
	   w[nrpa].nr=i;
	   w[nrpa].p=v[i];
	   nrpa++;
	   }
for(i=0;i<nrpa;++i) w[i].sd=dist(w[i].p.x,w[i].p.y);
qsrt(0,nrpa-1);
if(w[0].sd<sdmed){
	xi=w[0].p.x;
	yi=w[0].p.y;
	}
finish:
printf("%0.4lf %0.4lf\n",xi,yi);
return 0;
}