⚠️ Warning: This is a draft ⚠️

This means it might contain formatting issues, incorrect code, conceptual problems, or other severe issues.

If you want to help to improve and eventually enable this page, please fork RosettaGit's repository and open a merge request on GitHub.

{{collection|Closest pair problem}}

{{works with|GNUstep}}

{{works with|Cocoa}}

```
#import <math.h>

@interface Point : NSObject {
double xCoord, yCoord;
}
+ (instancetype)x: (double)x y: (double)y;
- (instancetype)initWithX: (double)x andY: (double)y;
- (double)x;
- (double)y;
- (double)dist: (Point *)pt;
- (NSComparisonResult)compareX: (Point *)pt;
- (NSComparisonResult)compareY: (Point *)pt;
@end

@implementation Point

+ (instancetype)x: (double)x y: (double)y {
return [[self alloc] initWithX: x andY: y];
}

- (instancetype)initWithX: (double)x andY: (double)y {
if ((self = [super init])) {
xCoord = x;
yCoord = y;
}
return self;
}

- (double)x { return xCoord; }
- (double)y { return yCoord; }

- (double)dist: (Point *)pt {
return hypot([self x] - [pt x], [self y] - [pt y]);
}

- (NSComparisonResult)compareX: (Point *)pt {
if      ( [self x] < [pt x] ) return NSOrderedAscending;
else if ( [self x] > [pt x] ) return NSOrderedDescending;
else                          return NSOrderedSame;
}

- (NSComparisonResult)compareY: (Point *)pt {
if      ( [self y] < [pt y] ) return NSOrderedAscending;
else if ( [self y] > [pt y] ) return NSOrderedDescending;
else                          return NSOrderedSame;
}
@end
```
```@interface ClosestPair : NSObject
+ (NSArray *)closestPairSimple: (NSArray *)pts;
+ (NSArray *)closestPair: (NSArray *)pts;
+ (NSArray *)closestPairPriv: (NSArray *)xP and: (NSArray *)yP;
+ (id)minBetween: (id)minA and: (id)minB;
@end

@implementation ClosestPair

+ (NSArray *)closestPairSimple: (NSArray *)pts {
if ( [pts count] < 2 ) return @[ @HUGE_VAL ];
double c = [ pts[0] dist: pts[1] ];
NSArray *r = @[ @(c), pts[0], pts[1] ];
for(int i=0; i < ([pts count] - 1); i++) {
for(int j=i+1; j < [pts count]; j++) {
double t = [ pts[i] dist: pts[j] ];
if ( t < c ) {
c = t;
r = @[ @(t), pts[i], pts[j] ];
}
}
}
return r;
}

+ (NSArray *)closestPair: (NSArray *)pts {
return [self closestPairPriv: [pts sortedArrayUsingSelector: @selector(compareX:)]
and: [pts sortedArrayUsingSelector: @selector(compareY:)]
];
}

+ (NSArray *)closestPairPriv: (NSArray *)xP and: (NSArray *)yP {
int nP, k;

if ( [xP count] <= 3 ) {
return [self closestPairSimple: xP];
} else {
int midx = ceil([xP count]/2.0);
NSArray *pL = [xP subarrayWithRange: NSMakeRange(0, midx)];
NSArray *pR = [xP subarrayWithRange: NSMakeRange(midx, [xP count] - midx)];
NSMutableArray *yL = [[NSMutableArray alloc] init];
NSMutableArray *yR = [[NSMutableArray alloc] init];
double middleVLine = [pL[midx-1] x];
for(int i=0; i < [yP count]; i++) {
if ( [yP[i] x] <= middleVLine ) {
} else {
}
}
NSArray *minR = [ClosestPair closestPairPriv: pR and: yR];
NSArray *minL = [ClosestPair closestPairPriv: pL and: yL];
NSMutableArray *minDist = [ClosestPair minBetween: minR and: minL];
NSMutableArray *joiningStrip = [NSMutableArray arrayWithCapacity: [xP count]];
for(int i=0; i < [yP count]; i++) {
if ( fabs([yP[i] x] - middleVLine) <
[minDist[0] doubleValue] ) {
}
}
NSMutableArray *tDist = minDist;
int nP = [joiningStrip count];
for(int i=0; i < (nP - 1); i++) {
int k = i + 1;
while( (k < nP) &&
( ([joiningStrip[k] y] - [joiningStrip[i] y]) < [minDist[0] doubleValue] ) ) {
double d = [joiningStrip[i] dist: joiningStrip[k]];
if ( d < [tDist[0] doubleValue] ) {
tDist = @[ @(d), joiningStrip[i], joiningStrip[k] ];
}
k++;
}
}
return tDist;
}
}

+ (id)minBetween: (id)minA and: (id)minB {
if ( [minA[0] doubleValue] < [minB[0] doubleValue] ) {
return minA;
} else {
return minB;
}
}

@end
```

'''Testing'''

```#define NP 10000

int main()
{
@autoreleasepool {

NSMutableArray *p = [[NSMutableArray alloc] init];
srand(0);
for(int i = 0; i < NP; i++) {
[Point x: 20.0*((double)rand()/(RAND_MAX+1.0)) - 10.0
y: 20.0*((double)rand()/(RAND_MAX+1.0)) - 10.0]
];
}

//NSArray *r1 = [ClosestPair closestPairSimple: p];
NSArray *r2 = [ClosestPair closestPair: p];

//NSLog(@"%lf", [r1[0] doubleValue]);
NSLog(@"%lf", [r2[0] doubleValue]);

}
return EXIT_SUCCESS;
}
```

Timing (with the time command):

```d&amp;c:         0.22user 0.00system 0:00.41elapsed
brute force: 13.53user 0.06system 0:13.87elapsed
```