Cod sursa(job #679717)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 13 februarie 2012 17:40:14
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<cstdio>
#include<fstream>
#include<cmath>
using namespace std;
int n,i,m;
struct pc{int x,y;}v[100002];
bool cond(pc i,pc j)
{
	return i.x<j.x;
}
double dist(int a,int b)
{
	return sqrtf( (v[a].x-v[b].x) * (v[a].x-v[b].x) + (v[a].y-v[b].y) * (v[a].y-v[b].y) );
}
double rezolva(long d,double rez)
{   //d->ordonada punctului central
	long i,j;
	double p;
	for(i=1;i<=n;++i)
		if( v[i].x<=d+rez && v[i].x>=d-rez )m++;
	for(i=1;i<=m;++i)
	 for(j=i+1;j<=i+7&&j<=m;++j)
	 {
		p=dist(i,j);
		if(p<rez)
			rez=p;
	 }
  return rez;
}

int main()
{
	freopen("cmap.in","r",stdin);freopen("cmap.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d %d",&v[i].x,&v[i].y);
	sort(v+1,v+n+1,cond);
	printf("%f", rezolva(v[(n+1)/2].x,1000000) );
return 0;}