Cod sursa(job #1535654)

Utilizator ManuNNazare Emanuel ManuN Data 25 noiembrie 2015 00:12:43
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.62 kb
import java.io.IOException;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.*;
import java.util.*;
imort java.io.*;
public class Punct implements Comparator<Punct>, Comparable<Punct>{
	double x,y;
	Punct(){}
	Punct(double a,double b)
	{
		x=a; y=b;
	}
	double getx()
	{
		return x;
	}
	double gety()
	{
		return y;
	}
	double dist(Punct o)
	{
		return Math.sqrt((this.x-o.x)*(this.x-o.x)+(this.y-o.y)*(this.y-o.y));
	}
	public int compareTo(Punct ob)
	{
		if(this.x-ob.x<0)
			return -1;
		else
			if(this.x-ob.x==0)
				return 0;
		return 1;
	}
	public int compare(Punct ob1,Punct ob2)
	{
		if(ob1.y-ob2.y<0)
			return -1;
		else
			if(ob1.y-ob2.y==0)
				return 0;
		return 1;
	}
	public String toString()
	{
		return (x+" "+y+'\n');
	}

	public static void main(String[] arg) throws IOException
	{
		int a,b;
		ArrayList<Punct> list=new ArrayList<>();
		Path filePath = Paths.get("cmap.in");
		Scanner scanner = new Scanner(filePath);
		while (scanner.hasNext())
		{
		    if (scanner.hasNextInt()) 
		    {
		    	a=scanner.nextInt();
		    	b=scanner.nextInt();
		    	Punct ob=new Punct(a,b);
		        list.add(ob);
		    } 
		    else 
		    {
		        scanner.next();
		    }
		}
		Collections.sort(list);
		try
            {
                File fac = new File("factoriales.txt");
                if (!fac.exists())
                {
                    fac.createNewFile();
                }
                
                FileWriter write = new FileWriter(fac);
                write.write(""+divideetimpera(list,0,list.size()-1));
                write.close();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
        }
		//System.out.println(list);
		//System.out.println(divideetimpera(list,0,list.size()-1));
		//divideetimpera(list,0,list.size()-1);
		//Collections.sort(list,new Punct());
		//System.out.println();
		//System.out.println(list);
		//System.out.println(list.size());
		scanner.close();
	}
	public static double divideetimpera(ArrayList<Punct> list,int ic,int sf)
	{
		if(sf-ic==1)
		{
			//System.out.println(2+" "+list.get(ic).dist(list.get(ic+1)));
			return list.get(ic).dist(list.get(ic+1));
		}
		else
		{
			if(sf-ic==2)
			{
				double min;
				min=list.get(ic).dist(list.get(ic+1));
				if(min<list.get(ic).dist(list.get(ic+2)))
					min=list.get(ic).dist(list.get(ic+2));
				if(min<list.get(ic+1).dist(list.get(ic+2)))
						min=list.get(ic+1).dist(list.get(ic+2));
				//System.out.println(3+" "+min);
				return min;
			}
			else
			{
				double y,x;
				x=divideetimpera(list,ic,(sf+ic)/2);
				y=divideetimpera(list,(sf+ic)/2+1,sf);
				//System.out.println(x+" "+y);
				if(x>y)
					x=y;
				y=combina(list,(sf+ic)/2,x);
				if(x<y)
					return x;
				else
					return y;
			}
		}
	}
	public static double combina(ArrayList<Punct> list,int m,double mn)
	{
		ArrayList<Punct> y=new ArrayList<>();
		for(int i=m-1;i>=0;i--)
			if(list.get(m).getx()-list.get(i).getx()>mn)
				break;
			else
				y.add(list.get(i));
		for(int i=m+1;i<list.size();i++)
			if(list.get(m).getx()-list.get(i).getx()>mn)
				break;
			else
				y.add(list.get(i));
		Collections.sort(y, new Punct());
		if(y.size()>7)
		{
			for(int i=0;i<y.size()-7;i++)
				for(int j=i+1;j<=i+7;j++)
					if(y.get(i).dist(y.get(j))<mn)
						mn=y.get(i).dist(y.get(j));
		}
		else
		{
			for(int i=0;i<y.size();i++)
				for(int j=i+1;j<y.size();j++)
					if(y.get(i).dist(y.get(j))<mn)
						mn=y.get(i).dist(y.get(j));
		}
		return mn;
	}
}