Cod sursa(job #1850281)

Utilizator CODEDESTROYER666Bogdan Sefcic CODEDESTROYER666 Data 18 ianuarie 2017 14:29:18
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.05 kb
import java.util.*;
import java.io.*;

public class Punct {
	private int x,y;
	public Punct()
	{
		setX(0);
		setY(0);
	}
	public Punct(int a, int b)
	{
		setX(a);
		setY(b);
	}
	public int getX() {
		return x;
	}
	public void setX(int x) {
		this.x = x;
	}
	public int getY() {
		return y;
	}
	public void setY(int y) {
		this.y = y;
	}
	
	
}

public class Main {

	private static Scanner s;
	public static double distanta(Punct a, Punct b)
	{
		return Math.sqrt((a.getX()-b.getX())*(a.getX()-b.getX())+(a.getY()-b.getY())*(a.getY()-b.getY()));
	}
	
	static double gasireScurta(ArrayList<Punct> pct, int n)
	{
		double min=Double.MAX_VALUE;
		for(int i=0;i<n;i++)
			for(int j=i+1;j<n;j++)
				min=distanta(pct.get(i),pct.get(j));
		return min;
	}
	
	static double bandaApropiate(ArrayList<Punct> p,int n,double d)
	{
		double min=d;
		for(int i=0;i<n;i++)
			for(int j=i+1;j<n && (p.get(j).getY()-p.get(i).getY())<min;j++)
				min=distanta(p.get(i),p.get(j));
		return min;
	}
	
	static double gasesteApropiate(ArrayList<Punct> pctX, ArrayList<Punct> pctY,int n)
	{
		if(n<=3)return gasireScurta(pctX,n);
		int m=n/2;
		Punct mijloc=pctX.get(m);
		ArrayList<Punct> stanga=new ArrayList<Punct>();
		ArrayList<Punct> dreapta=new ArrayList<Punct>();
		int istg=0,idr=0;
		for(int i=0;i<pctY.size();i++)
		{
			if(pctY.get(i).getX()<=mijloc.getX()){
			
				stanga.add(pctY.get(i));
				istg++;
			}
			else{
				dreapta.add( pctY.get(i));
				idr++;
			}
		}
		ArrayList<Punct> aux=new ArrayList<Punct>();
		for(int i=m;i<pctX.size();i++)
		{
			aux.add(pctX.get(i));
		}
		double stg=gasesteApropiate(pctX,stanga,m);
		double dr=gasesteApropiate(aux,dreapta,n-m);
		double d=Math.min(dr,stg);
		ArrayList<Punct> banda=new ArrayList<Punct>();
		int j=0;
		for(int i=0;i<pctY.size();i++)
			if(Math.abs(pctY.get(i).getX()-mijloc.getX())<d)
				{
					banda.add(pctY.get(i));
					j++;
				}
		return Math.min(d, bandaApropiate(banda,j,d));
	}
	
	static double celeMaiApropiate(ArrayList<Punct> pct,int n)
	{
		ArrayList<Punct> pctX=new ArrayList<Punct>();
		ArrayList<Punct> pctY=new ArrayList<Punct>();
		
		for(int i=0;i<n;i++)
		{
			pctX.add(pct.get(i));
			pctY.add(pct.get(i));
		}
		pctX.sort(new Comparator<Punct>(){
			public int compare(Punct a, Punct b)
			{
				return a.getX()-b.getX();
			}
		});
		pctY.sort(new Comparator<Punct>(){
			public int compare(Punct a, Punct b)
			{
				return a.getY()-b.getY();
			}
		});
		return gasesteApropiate(pctX,pctY,n);
	}
	public static void main(String[] args)
	{
		try {
			s = new Scanner(new File("date.in"));
			int n=s.nextInt();
			ArrayList<Punct> puncte=new ArrayList<Punct>();
			for(int i=0;i<n;i++)
			{
				Punct p=new Punct(s.nextInt(),s.nextInt());
				puncte.add(p);
			}
			double result=celeMaiApropiate(puncte,n);
			PrintWriter w=new PrintWriter("date.out");
			w.println(result);
			w.close();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
	}
}