rendered paste bodyimport java.lang.Math;
import java.util.*;
class PointTree {
public PointTree( double left, double top, double right, double bottom, PointTree parent ) {
this.point = null;
this.subTrees = null;
this.parent = parent;
this.left = left;
this.top = top;
this.right = right;
this.bottom = bottom;
this.horizontalMid = (this.left + this.right) / 2;
this.verticalMid = (this.bottom + this.top) / 2;
}
public void subAdd( Positioned added ) {
Point addedPos = added.getPos();
if ( addedPos.getX() < horizontalMid && addedPos.getY() < verticalMid )
subTrees[0].add( added );
else if ( addedPos.getX() > horizontalMid && addedPos.getY() < verticalMid )
subTrees[1].add( added );
else if ( addedPos.getX() < horizontalMid && addedPos.getY() > verticalMid )
subTrees[2].add( added );
else if ( addedPos.getX() > horizontalMid && addedPos.getY() > verticalMid )
subTrees[3].add( added );
}
public void add( Positioned added ) {
Point addedPos = added.getPos();
if ( subTrees != null ) {
subAdd( added );
} else if ( point == null ) {
this.point = added;
} else {
Point currPos = this.point.getPos();
if ( Math.abs( addedPos.getX() - currPos.getX() ) < 0.001 &&
Math.abs( addedPos.getY() - currPos.getY() ) < 0.001 ) {
return;
} else {
PointTree lt = new PointTree( left, top, horizontalMid, verticalMid, this );
PointTree rt = new PointTree( horizontalMid, top, right, verticalMid, this );
PointTree lb = new PointTree( left, verticalMid, horizontalMid, bottom, this );
PointTree rb = new PointTree( horizontalMid, verticalMid, right, bottom, this );
subTrees = new PointTree[4];
subTrees[0] = lt;
subTrees[1] = rt;
subTrees[2] = lb;
subTrees[3] = rb;
subAdd( point );
subAdd( added );
point = null;
}
}
}
public boolean isEmpty() {
return subTrees == null && point == null;
}
public boolean isNode() {
return subTrees == null;
}
public void contract() {
int empties = 0;
PointTree notEmpty = null;
if ( subTrees[0].isEmpty() ) empties++;
else notEmpty = subTrees[0];
if ( subTrees[1].isEmpty() ) empties++;
else notEmpty = subTrees[1];
if ( subTrees[2].isEmpty() ) empties++;
else notEmpty = subTrees[2];
if ( subTrees[3].isEmpty() ) empties++;
else notEmpty = subTrees[3];
if ( empties == 4 ) {
subTrees = null;
if (parent != null)
parent.contract();
} else if ( empties == 3 ) {
if ( notEmpty.isNode() ) {
point = notEmpty.point;
subTrees = null;
}
}
}
public void subRem( Positioned remed ) {
Point remedPos = remed.getPos();
if ( remedPos.getX() < horizontalMid && remedPos.getY() < verticalMid )
subTrees[0].rem( remed );
else if ( remedPos.getX() > horizontalMid && remedPos.getY() < verticalMid )
subTrees[1].rem( remed );
else if ( remedPos.getX() < horizontalMid && remedPos.getY() > verticalMid )
subTrees[2].rem( remed );
else if ( remedPos.getX() > horizontalMid && remedPos.getY() > verticalMid )
subTrees[3].rem( remed );
}
public void rem( Positioned remed ) {
Point remedPos = remed.getPos();
if ( subTrees != null ) {
subRem( remed );
} else if ( point == null ) {
// can't find (LOL) point to remove lolz
} else if ( point == remed ) {
point = null;
parent.contract();
} else {
// nothing founds xxxxxxxD
}
}
public int inWhich( Positioned point ) {
Point pointPos = point.getPos();
if ( pointPos.getX() < horizontalMid &&
pointPos.getY() < verticalMid ) return 0;
if ( pointPos.getX() >= horizontalMid &&
pointPos.getY() < verticalMid ) return 1;
if ( pointPos.getX() < horizontalMid &&
pointPos.getY() >= verticalMid ) return 2;
if ( pointPos.getX() >= horizontalMid &&
pointPos.getY() >= verticalMid ) return 3;
return -1;
}
public ArrayList<Positioned> getAll() {
ArrayList<Positioned> ret = new ArrayList<Positioned>();
if ( subTrees == null ) {
if ( point != null ) ret.add( point );
} else {
for ( PointTree subTree : subTrees ) {
ret.addAll( subTree.getAll() );
}
}
return ret;
}
public PointTree getSubTree( int subTreeIdx ) {
if ( subTrees == null ) { return this; }
else return subTrees[subTreeIdx];
}
public PointTree getParent() {
if ( parent == null ) return this;
else return parent;
}
public PointTree[] getSubTrees() { return subTrees; }
public int oppositeOf( int dir ) { return 3 - dir; }
// find the submost PointTrees
public ArrayList<Positioned> closestOnes( Positioned searched, PointTree[] pieces, int containedIdx ) {
Point searchedPos = searched.getPos();
System.out.println( toString() );
System.out.println( "" );
System.out.println( "" );
System.out.println( "" );
while ( pieces[ containedIdx ].subTrees != null ) {
System.out.println( pieces[ containedIdx ].toString() );
System.out.println( pieces[ containedIdx ].left );
System.out.println( pieces[ containedIdx ].top );
System.out.println( pieces[ containedIdx ].right );
System.out.println( pieces[ containedIdx ].bottom );
int nextSubIdx = pieces[ containedIdx ].inWhich( searched );
System.out.println( containedIdx );
System.out.println( nextSubIdx );
System.out.println( "" );
System.out.println( "" );
System.out.println( "" );
// going the opposite direction as last
if ( nextSubIdx == oppositeOf( containedIdx ) ) {
for ( int i = 0; i < 4; i++ ) {
pieces[i] = pieces[i].getSubTree(i);
}
//containedIdx = oppositeOf( containedIdx );
// going deeper in the previous direction
} else if ( nextSubIdx == containedIdx ) {
System.out.println("ooookokokoko");
pieces = getParent().getSubTrees();
pieces[0] = pieces[0].getSubTree( 3 );
pieces[1] = pieces[1].getSubTree( 2 );
pieces[2] = pieces[2].getSubTree( 1 );
pieces[3] = pieces[3].getSubTree( 0 );
containedIdx = oppositeOf( containedIdx );
} else {
System.out.println( ";;)");
// separately handle the other 8 cases :DD
if ( nextSubIdx == 1 && containedIdx == 0 ) {
// p[0].ur, p[0].par.ur.lr, p[1].par.ul.ll, p[1].ul
PointTree a = pieces[0].getSubTree( 1 );
PointTree b = pieces[0].getParent().getSubTree(1).getSubTree(3);
PointTree c = pieces[1].getParent().getSubTree(0).getSubTree(2);
PointTree d = pieces[1].getSubTree(0);
pieces[0] = a;
pieces[1] = b;
pieces[2] = c;
pieces[3] = d;
} else if ( nextSubIdx == 2 && containedIdx == 0 ) {
// p[0].ll, p[0].par.ll.lr, p[2].par.ul.ur, p[2].ul
PointTree a = pieces[0].getSubTree( 2 );
PointTree b = pieces[0].getParent().getSubTree(2).getSubTree(3);
PointTree c = pieces[2].getParent().getSubTree(0).getSubTree(1);
PointTree d = pieces[2].getSubTree(0);
pieces[0] = a;
pieces[1] = b;
pieces[2] = c;
pieces[3] = d;
} else if ( nextSubIdx == 0 && containedIdx == 1 ) {
// p[1].ul, p[1].par.ul.ll, p[0].par.ur.lr, p[0].ur
PointTree a = pieces[1].getSubTree( 0 );
PointTree b = pieces[1].getParent().getSubTree(0).getSubTree(2);
PointTree c = pieces[0].getParent().getSubTree(1).getSubTree(3);
PointTree d = pieces[0].getSubTree(1);
pieces[0] = a;
pieces[1] = b;
pieces[2] = c;
pieces[3] = d;
} else if ( nextSubIdx == 3 && containedIdx == 1 ) {
// p[1].lr, p[1].par.lr.ll, p[3].par.ur.ul, p[3].ur
PointTree a = pieces[1].getSubTree( 3 );
PointTree b = pieces[1].getParent().getSubTree(3).getSubTree(2);
PointTree c = pieces[3].getParent().getSubTree(1).getSubTree(0);
PointTree d = pieces[3].getSubTree(1);
pieces[0] = a;
pieces[1] = b;
pieces[2] = c;
pieces[3] = d;
} else if ( nextSubIdx == 0 && containedIdx == 2 ) {
// p[2].ul, p[2].par.ul.ur, p[0].par.ll.lr, p[0].ll
PointTree a = pieces[2].getSubTree( 0 );
PointTree b = pieces[2].getParent().getSubTree(0).getSubTree(1);
PointTree c = pieces[0].getParent().getSubTree(2).getSubTree(3);
PointTree d = pieces[0].getSubTree(2);
pieces[0] = a;
pieces[1] = b;
pieces[2] = c;
pieces[3] = d;
} else if ( nextSubIdx == 3 && containedIdx == 2 ) {
// p[2].lr, p[2].par.lr.ur, p[3].par.ll.ul, p[3].ll
PointTree a = pieces[2].getSubTree( 3 );
PointTree b = pieces[2].getParent().getSubTree(3).getSubTree(1);
PointTree c = pieces[3].getParent().getSubTree(2).getSubTree(0);
PointTree d = pieces[3].getSubTree(2);
pieces[0] = a;
pieces[1] = b;
pieces[2] = c;
pieces[3] = d;
} else if ( nextSubIdx == 1 && containedIdx == 3 ) {
// p[3].ur, p[3].par.ur.ul, p[1].par.lr.ll, p[1].lr
PointTree a = pieces[3].getSubTree( 1 );
PointTree b = pieces[3].getParent().getSubTree(1).getSubTree(0);
PointTree c = pieces[1].getParent().getSubTree(3).getSubTree(2);
PointTree d = pieces[1].getSubTree(3);
pieces[0] = a;
pieces[1] = b;
pieces[2] = c;
pieces[3] = d;
} else if ( nextSubIdx == 2 && containedIdx == 3 ) {
// p[3].ll, p[3].par.ll.ul, p[2].par.lr.ur, p[2].lr
PointTree a = pieces[3].getSubTree( 2 );
PointTree b = pieces[3].getParent().getSubTree(2).getSubTree(0);
PointTree c = pieces[2].getParent().getSubTree(3).getSubTree(1);
PointTree d = pieces[2].getSubTree(3);
pieces[0] = a;
pieces[1] = b;
pieces[2] = c;
pieces[3] = d;
}
}
}
ArrayList<Positioned> ret = new ArrayList<Positioned>();
for ( PointTree p : pieces ) {
ret.addAll( p.getParent().getAll() );
}
return ret;
}
// return closest from given set of points
public Positioned closestOf( Positioned searched, ArrayList<Positioned> points ) {
Point searchedPos = searched.getPos();
Point closest = null;
double minDistance = -1;
for( Positioned point : points ) {
Point pointPos = point.getPos();
double distance = pointPos.distanceTo( searchedPos );
if( minDistance<0 || distance<minDistance ) {
minDistance = distance;
closest = pointPos;
}
}
return closest;
}
// return point closest to searched
public Positioned closestTo( Positioned searched ) {
if (subTrees == null) {
return point;
} else {
int containedIdx = inWhich( searched );
ArrayList<Positioned> closests = closestOnes( searched, subTrees, containedIdx );
System.out.println( closests.toString() );
return closestOf( searched, closests);
}
}
public String toString() {
if ( subTrees != null ) {
return "{" + subTrees[0].toString() + ", " +
subTrees[1].toString() + ", " +
subTrees[2].toString() + ", " +
subTrees[3].toString() + "}";
} else if ( point != null ) {
return point.getPos().toString();
} else {
return "*";
}
}
private Positioned point;
private PointTree[] subTrees;
private PointTree parent;
private double left;
private double top;
private double right;
private double bottom;
private double horizontalMid;
private double verticalMid;
}
class Pair <CarType extends Comparable, CdrType> implements Comparable {
public Pair() {
this.car = null;
this.cdr = null;
}
public Pair( CarType car, CdrType cdr ) {
this.car = car;
this.cdr = cdr;
}
public int compareTo( Object p ) {
return car.compareTo( ((Pair) p).getCar() );
}
public void setCar( CarType newValue ) {
car = newValue;
}
public void setCdr( CdrType newValue ) {
cdr = newValue;
}
public CarType getCar() {
return car;
}
public CdrType getCdr() {
return cdr;
}
private CarType car;
private CdrType cdr;
}
// elements are intersperced every
class DynamicSortedArray<K extends Comparable, V> {
public DynamicSortedArray(int spaces, int capacity) {
this.spaces = spaces;
int realCapacity = capacity * ( spaces + 1 );
list = new ArrayList< Pair< K, V > >( realCapacity );
}
// find the next non null value to the right
public int fixIdx( int idx ) {
while ( idx < list.size() && list.get( idx ) == null )
idx++;
return idx;
}
public int fixIdxBackw( int idx ) {
while ( idx >= 0 && list.get( idx ) == null )
idx--;
return idx;
}
// fix gaps, they are either too big or too small
public void fix() {
ArrayList< Pair<K, V> > newList = new ArrayList< Pair<K, V> > ( list.size() );
for( int il = 0; il < list.size(); il++) {
il = fixIdx( il );
if ( il >= list.size() ) break;
for (int is = 0; is < spaces; is++ ) {
newList.add( null );
}
newList.add( list.get( il ) );
}
list = newList;
}
public void remGaps() {
int reali = 0;
int puti = 0;
while ( reali < list.size() ) {
if ( list.get(reali) != null ) {
list.set( puti, list.get(reali) );
puti++;
}
reali++;
}
}
public void sortAndFix() {
remGaps();
Object[] sortee = list.toArray();
Arrays.sort( sortee );
list.clear();
for ( Object x : sortee ) {
list.add( (Pair<K, V>)x );
}
fix();
}
// find rightmost neighbor, the actual position if obj in list, or size of list
public int find( K key, int a, int b ) {
/* DEBUG:
System.out.println( "as" );
System.out.println( a );
System.out.println( b );
System.out.println( this.toString() );
*/
if ( a == b) {
return a;
} else {
int midIdx = fixIdx( (a+b)/2 );
if ( midIdx == list.size() ) {
fix();
return list.size();
} else if ( midIdx == b ) {
Pair<K, V> valAtA = list.get( a );
if ( valAtA != null && valAtA.getCar().equals( key ) ) return a;
return b;
}
K pivot = list.get( midIdx ).getCar();
int cmp = key.compareTo( pivot );
if ( cmp == 0 ) {
return midIdx;
} else if ( cmp < 0 ) {
return find( key, a, midIdx );
} else if ( cmp > 0 ) {
return find( key, midIdx + 1, b );
}
return 0; // this is never reached
}
}
public int find( K key ) {
if ( list.isEmpty() ) {
return 0;
} else {
return find( key, 0, list.size() );
}
}
public void rawAdd( K key, V val ) {
list.add( new Pair<K, V>(key, val));
}
public void add( K key, V val ) {
int idx = find( key );
Pair<K, V> kvPair = new Pair<K, V>( key, val );
// DEBUG: System.out.println( idx );
if ( idx >= list.size() ) {
for ( int i = 0; i < spaces; i++ ) {
list.add( null );
}
list.add( kvPair );
} else {
if ( list.get( idx - 1 ) == null ) {
list.set( idx - 1, kvPair );
} else {
// obviously corrupt, so fix all gaps!
// DEBUG System.out.println( "kuli..." );
fix();
// retry adding (guaranteed to work this time)
add( key, val );
}
}
}
public int size() {
return list.size();
}
public boolean isEmpty() {
return list.isEmpty();
}
public V rawGet( int idx ) {
return list.get( idx ).getCdr();
}
public int exactIdx( K key, V val ) {
int idxNext = find( key );
int idxPrev = idxNext;
while ( idxNext < list.size() &&
list.get( idxNext ).getCar().equals( key ) ) {
if ( list.get( idxNext ).getCdr().equals( val ) ) {
return idxNext;
}
idxNext = fixIdx( idxNext + 1 );
}
while ( idxPrev >= 0 &&
list.get( idxPrev ).getCar().equals( key ) ) {
if ( list.get( idxPrev ).getCdr().equals( val ) ) {
return idxPrev;
}
idxPrev = fixIdxBackw( idxPrev - 1 );
}
return -1;
}
public void rem( K key, V val ) {
int idx = exactIdx( key, val );
if ( idx != -1 ) {
list.set( idx, null );
maybeFixAt( idx );
}
}
public void maybeFixAt( int idx ) {
boolean leftOkay = false;
boolean rightOkay = false;
for ( int i = 1; i <= 2*spaces; i++ ) {
if ( idx - i < 0 ) leftOkay = true;
else if ( list.get( idx - i ) != null ) leftOkay = true;
if ( idx + i >= list.size() ) rightOkay = true;
else if ( list.get( idx + i ) != null ) rightOkay = true;
}
if ( !leftOkay || !rightOkay )
fix();
}
public String toString() {
String ret = "";
for ( Pair<K, V> i : list ) {
if ( i == null ) {
ret += "* ";
} else {
ret += i.getCar().toString() + ":" + i.getCdr().toString() + " ";
}
}
return ret;
}
private int spaces;
private ArrayList< Pair< K, V > > list;
}
class OrderedStorer {
public OrderedStorer ( int spaces, int capacity ) {
xAxisLookup = new DynamicSortedArray<Double, Positioned>( spaces, capacity );
yAxisLookup = new DynamicSortedArray<Double, Positioned>( spaces, capacity );
}
public void add(Positioned added) {
Point addedPos = added.getPos();
xAxisLookup.add( addedPos.getX(), added );
yAxisLookup.add( addedPos.getY(), added );
}
public void rawAdd(Positioned added) {
Point addedPos = added.getPos();
xAxisLookup.rawAdd( addedPos.getX(), added );
yAxisLookup.rawAdd( addedPos.getY(), added );
}
public void sortAndFix() {
xAxisLookup.sortAndFix();
yAxisLookup.sortAndFix();
}
public void rem(Positioned remed) {
Point remedPos = remed.getPos();
xAxisLookup.rem( remedPos.getX(), remed );
yAxisLookup.rem( remedPos.getY(), remed );
}
public Positioned closestTo(Positioned searched) {
if ( xAxisLookup.isEmpty() ) return null;
Point searchedPos = searched.getPos();
int xNext = xAxisLookup.find( searchedPos.getX() );
int xPrev = xAxisLookup.fixIdxBackw( xNext - 1 );
int yNext = yAxisLookup.find( searchedPos.getY() );
int yPrev = yAxisLookup.fixIdxBackw( yNext - 1 );
Positioned closestPoint = xAxisLookup.rawGet( xAxisLookup.fixIdx(0) );
double bestDist = closestPoint.getPos().distanceTo( searchedPos );
Positioned curr = null;
double currDist = 0;
while ( xPrev >= 0 || xNext < xAxisLookup.size() ||
yPrev >= 0 || yNext < yAxisLookup.size()) {
//System.out.println( currDist );
//System.out.println( bestDist );
//System.out.println( xPrev );
//System.out.println( xNext );
//System.out.println( yPrev );
//System.out.println( yNext );
if ( xPrev >= 0 ) {
curr = xAxisLookup.rawGet( xPrev );
currDist = curr.getPos().distanceTo( searchedPos );
if ( currDist < bestDist ) {
closestPoint = curr;
bestDist = currDist;
} else {
// the "clever" part, shortcut if too far x-wise
if ( Math.abs( searchedPos.getX() - curr.getPos().getX() ) > bestDist) {
xPrev = -1;
} else {
//System.out.println("xprevlol");
//System.out.println( Math.abs( searchedPos.getX() - curr.getPos().getX() ) );
}
}
xPrev = xAxisLookup.fixIdxBackw( xPrev - 1);
}
if ( xNext < xAxisLookup.size() ) {
curr = xAxisLookup.rawGet( xNext );
currDist = curr.getPos().distanceTo( searchedPos );
if ( currDist < bestDist ) {
closestPoint = curr;
bestDist = currDist;
} else {
// the "clever" part, shortcut if too far x-wise
if ( Math.abs( searchedPos.getX() - curr.getPos().getX() ) > bestDist) {
xNext = xAxisLookup.size();
} else {
//System.out.println("xnextlol");
//System.out.println( Math.abs( searchedPos.getX() - curr.getPos().getX() ) );
}
}
xNext = xAxisLookup.fixIdx( xNext + 1);
}
if ( yPrev >= 0 ) {
curr = yAxisLookup.rawGet( yPrev );
currDist = curr.getPos().distanceTo( searchedPos );
if ( currDist < bestDist ) {
closestPoint = curr;
bestDist = currDist;
} else {
// the "clever" part, shortcut if too far y-wise
if ( Math.abs( searchedPos.getY() - curr.getPos().getY() ) > bestDist) {
yPrev = -1;
} else {
//System.out.println("yprevlol");
//System.out.println( Math.abs( searchedPos.getY() - curr.getPos().getY() ) );
}
}
yPrev = yAxisLookup.fixIdxBackw( yPrev - 1);
}
if ( yNext < yAxisLookup.size() ) {
curr = yAxisLookup.rawGet( xNext );
currDist = curr.getPos().distanceTo( searchedPos );
if ( currDist < bestDist ) {
closestPoint = curr;
bestDist = currDist;
} else {
// the "clever" part, shortcut if too far y-wise
if ( Math.abs( searchedPos.getY() - curr.getPos().getY() ) > bestDist) {
yNext = yAxisLookup.size();
} else {
//System.out.println("ynextlol");
//System.out.println( Math.abs( searchedPos.getY() - curr.getPos().getY() ) );
}
}
yNext = yAxisLookup.fixIdx( yNext + 1);
}
//System.out.println( "" );
}
return closestPoint;
}
public String toString() {
return yAxisLookup.toString() + "\n\n" + xAxisLookup.toString();
}
DynamicSortedArray<Double, Positioned> xAxisLookup;
DynamicSortedArray<Double, Positioned> yAxisLookup;
}
class Storor {
public Storor( double left, double top, double right, double bottom ) {
pointTree = new PointTree(left, top, right, bottom, null);
orderedStorer = new OrderedStorer( 2, 256 );
}
public void add( Positioned p ) {
points.add( p );
orderedStorer.add( p );
//pointTree.add( p );
}
public void rawAdd( Positioned p ) {
points.add( p );
orderedStorer.rawAdd( p );
//pointTree.add( p );
}
public void sortAndFix() {
orderedStorer.sortAndFix();
}
public void rem( Positioned p ) {
points.remove( p );
orderedStorer.rem( p );
//pointTree.rem( p );
}
public ArrayList<Positioned> getAll() {
return points;
}
public Positioned closestTo( Positioned searched ) {
return orderedStorer.closestTo( searched ); // pointTree.closestTo( searched );
}
public Positioned slowClosestTo( Positioned searched ) {
Point searchedPos = searched.getPos();
Point closest = null;
double minDistance = -1;
for( Positioned point : points ) {
Point pointPos = point.getPos();
double distance = pointPos.distanceTo( searchedPos );
if( minDistance<0 || distance<minDistance ) {
minDistance = distance;
closest = pointPos;
}
}
return closest;
}
public String toString() {
return orderedStorer.toString();
}
private ArrayList<Positioned> points = new ArrayList<Positioned>();
private PointTree pointTree;
private OrderedStorer orderedStorer;
// testmain for storer löl :D
public static void _main( String[] args ) {
DynamicSortedArray<Double, String> d = new DynamicSortedArray<Double, String>( 2, 50 );
// Pair <Integer, Double> p = new Pair <Integer, Double> ();
d.add( 4.0, "neli" );
d.add( 4.0, "kuli" );
d.add( 4.0, "vili" );
d.add( 4.0, "voli" );
d.add( 4.0, "hili" );
d.add( 4.0, "hali" );
System.out.println( d.toString() );
d.rem( 4.0, "neli" );
System.out.println( d.toString() );
d.rem( 4.0, "kuli" );
System.out.println( d.toString() );
d.rem( 4.0, "voli" );
System.out.println( d.toString() );
}
/*
50 x 50
fast takes...
1785
slow takes...
16416
100 x 100
fast takes...
3640
slow takes...
60816
150 x 150
fast takes...
5304
slow takes...
131856
*/
public static void main( String[] args ) {
Storor s = new Storor( 0, 0, 5, 5 );
for ( int ix = 0; ix < 150; ix++ ) {
for ( int iy = 0; iy < 150; iy++ ) {
s.rawAdd( new Point( ix, iy ) );
}
}
System.out.println( "ok" );
s.sortAndFix();
System.out.println( "fof.." );
Random rander = new Random( 1 );
//while ( s.getAll().size() > 100 ) {
// int ridx = Math.abs( rander.nextInt() % s.getAll().size() );
// s.rawRem( s.getAll().get( ridx ) );
// System.out.println( s.toString() );
//}
System.out.println( "okol" );
//GregorianCalendar timer = ;
long time = (new GregorianCalendar()).getTimeInMillis();
System.out.println( "fast takes..." );
for(int i=0;i<1000;i++)s.closestTo( new Point( 32.2, 32.1 ));
//System.out.println( (Point)( s.closestTo( new Point( 32.2, 32.1 ) ) ) );
System.out.println( (new GregorianCalendar()).getTimeInMillis() - time );
time = (new GregorianCalendar()).getTimeInMillis();
System.out.println( "slow takes..." );
for(int i=0;i<1000;i++) s.slowClosestTo( new Point( 32.2, 32.1 ) );
System.out.println( (new GregorianCalendar()).getTimeInMillis() - time );
}
}
interface Positioned {
Point getPos();
}
class Point implements Positioned {
public Point (double x, double y) { this.x=x; this.y=y; }
public double getX() { return x; }
public double getY() { return y; }
public Point getPos() {
return this;
}
public double distanceTo( Point p ) {
double xDiff = p.getX() - x;
double yDiff = p.getY() - y;
return Math.sqrt( xDiff*xDiff + yDiff*yDiff );
}
public String toString() {
return "("+x+", "+y+")";
}
private double x;
private double y;
}