Pagini recente » Cod sursa (job #2778624) | Cod sursa (job #2225374) | Cod sursa (job #2227356) | Cod sursa (job #2580845) | Cod sursa (job #1817433)
import com.sun.istack.internal.Nullable;
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import com.sun.istack.internal.Nullable;
import sun.plugin.javascript.navig.Array;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
/**
* Created by balex on 27.11.2016.
*/
public class Infoarena{
public static void main(String[] args) throws Exception{
Map map = new Map("cmap.in");
PrintWriter out = new PrintWriter("cmap.out");
out.print(map.cmap());
out.flush();
System.out.print(map.cmap());
}
}
class Coordinate {
private int x, y;
public Coordinate(int x, int y){
this.x = x;
this.y = y;
}
public int getX(){
return x;
}
public int getY(){
return y;
}
public static double distance(Coordinate c1, Coordinate c2){
return Math.sqrt(Math.pow((c1.x-c2.x),2)+(Math.pow((c1.y-c2.y),2)));
}
public boolean hasXBetween(double leftBound, double rightBound){
return (this.x>leftBound && this.x<rightBound);
}
}
class Map {
private Coordinate[] coordsSortedByX;
private Coordinate[] coordsSortedByY;
private int coordinatesNo;
////
Map(String fileName){
try{
Coordinate[] coordinates;
Scanner in = new Scanner(new File(fileName));
coordinatesNo = in.nextInt();
coordinates = new Coordinate[coordinatesNo];
for(int i=0;i<coordinatesNo;i++){
coordinates[i] = new Coordinate(in.nextInt(),in.nextInt());
}
coordsSortedByX = sortByX(coordinates);
coordsSortedByY = sortByY(coordinates);
}catch (FileNotFoundException e){System.out.println("Error");}
}
private Coordinate[] sortByX(Coordinate[] coordinates) {
Arrays.sort(coordinates, new Comparator<Coordinate>() {
@Override
public int compare(Coordinate c1, Coordinate c2) {
if(c1.getX() == c2.getX())
return 0;
return c1.getX() < c2.getX() ? -1 : 1;
}
});
return coordinates;
}
private Coordinate[] sortByY(Coordinate[] coordinates) {
Arrays.sort(coordinates, new Comparator<Coordinate>() {
@Override
public int compare(Coordinate c1, Coordinate c2) {
if(c1.getY() == c2.getY())
return 0;
return c1.getY() < c2.getY() ? -1 : 1;
}
});
return coordinates;
}
public double cmap(){
return leastDistanceWithin(0,coordinatesNo-1);
}
private double leastDistanceWithin(int leftmostIndex, int rightmostIndex){ //O(nlogn)
if(leftmostIndex==rightmostIndex-1)
return Coordinate.distance(coordsSortedByX[leftmostIndex],coordsSortedByX[rightmostIndex]);
else {
double d1 = leastDistanceWithin(leftmostIndex, (leftmostIndex + rightmostIndex) / 2); //O(nlogn)
double d2 = leastDistanceWithin((leftmostIndex + rightmostIndex) / 2, rightmostIndex); //O(nlogn)
double δ = Math.min(d1, d2);
return Math.min(δ, leastDistanceAcross(δ, leftmostIndex, rightmostIndex));//O(n)
}
}
private double leastDistanceAcross(double borderSize, int leftmostIndex, int rightmostIndex){ //O(n)
double leastDistanceAcross = Double.MAX_VALUE;
ArrayList<Coordinate> coordsWithinBorder = filterCoordsWithinBorder((leftmostIndex+rightmostIndex)/2,borderSize); //O(n)
if(coordsWithinBorder != null)
for(int i=0;i<coordsWithinBorder.size()-1;i++){
for(int j=i+1;j<=Math.min(i+7,coordsWithinBorder.size()-1);j++){
if(Coordinate.distance(coordsSortedByX[i],coordsSortedByX[j])<leastDistanceAcross)
leastDistanceAcross = Coordinate.distance(coordsSortedByX[i],coordsSortedByX[j]);
}
}
return leastDistanceAcross;
}
@Nullable
private ArrayList<Coordinate> filterCoordsWithinBorder(int medianIndex, double borderSize) { //O(n)
ArrayList<Coordinate> coordsWithinBorder = new ArrayList<>();
double borderLeftBound = coordsSortedByX[medianIndex].getX()-borderSize;
double borderRightBound = coordsSortedByX[medianIndex].getX()+borderSize;
for(Coordinate c : coordsSortedByY){ //O(n)
if(c.hasXBetween(borderLeftBound,borderRightBound))
coordsWithinBorder.add(c);
}
return coordsWithinBorder.isEmpty()? null : coordsWithinBorder;
}
}