Pagini recente » Cod sursa (job #2140954) | Cod sursa (job #1016248) | Cod sursa (job #30858) | Cod sursa (job #1626290) | Cod sursa (job #1535657)
import java.io.IOException;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.*;
import 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;
}
}