Cod sursa(job #1825956)

Utilizator Alinnkb96Terinte Alin Alinnkb96 Data 9 decembrie 2016 21:43:27
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.44 kb
package cmap;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Writer;
import java.util.Scanner;



public class Cmap {
	
	static int n, mij, q;
	static double S = 1000000000;
	static punct[] p = new punct[100000];
	static punct[] pp = new punct[100000];
	static punct D ;
	
	
	public static class punct
	{
	   public int x;
	   public int y;
	   public void set(int a, int b) { x=a; y=b;}
	   punct() {}
	};

	boolean cmpx(punct a, punct b)
	{
	    return a.x < b.x;
	}
	
	boolean cmpy(punct a, punct b)
	{
	    return a.y < b.y;
	}
	
	public static void sortareP()
	{
		punct aux;
		for(int i=1 ; i<=n-1 ; i++)
			for(int j=i+1 ; j<=n ; j++)
				if(p[i].x < p[j].x)
				{
					aux = p[i];
					p[i] = p[j];
					p[j] = aux;
				}
	}
	
	public static void sortarePP()
	{
		punct aux;
		for(int i=1 ; i<=n-1 ; i++)
			for(int j=i+1 ; j<=n ; j++)
				if(pp[i].y < pp[j].y)
				{
					aux = pp[i];
					pp[i] = pp[j];
					pp[j] = aux;
				}
	}
		
	static void d_coord()
	{
	    mij = n/2;
	    D.x = p[mij].x;
	}
	
	static double euclid(int i, int j)
	{
	    return Math.sqrt( Math.pow((double)(p[i].x-p[j].x), (double)2) + Math.pow((double)(p[i].y-p[j].y), (double)2) );
	}

	
	public static void det_int()
	{
	    for(int i=1; i<=n; i++)
	        if(p[i].x <= D.x+S && p[i].x >= D.x-S)
	            pp[++q] = p[i];
	   sortarePP();
	}
	
	
	public static void solve()
	{
	    sortareP(); // sortat abscisa
	    d_coord(); // coord. dreptei D
	    det_int(); // punctele din intervalul 2*S
	    double dt;
	    for(int i=1; i<=q; i++)
	        for(int j=i+1; j<=i+7 && j<=q; j++)
	        {
	            dt = euclid(i, j);
	            if(dt < S)
	                S = dt;
	        }
	}
	
	public static void function()
	{
		p[1].x = 5;
	}
	
	
	public static void main(String[] args)
	throws FileNotFoundException , IOException {

		Scanner sc = new Scanner(new File("cmap.in"));
		Writer wr = new FileWriter("cmap.out");

		n = sc.nextInt();
		D = new punct();
		
		for(int i=1 ; i<=n ; i++)
		{
			p[i] = new punct();
			pp[i] = new punct();
			p[i].x = sc.nextInt();
			p[i].y = sc.nextInt();	
		}
	
		
		//function()
		solve();
		
		/*for(int i=1 ; i<=n ; i++)
		{
			wr.write(p[i].x + " " + p[i].y + "\n");
		}*/
		
		wr.write(S +"");
		
		sc.close();
		wr.close();
		
	}

}