Colinear points tests.

colinear.cpp

//
//  colinear.cpp
//  AlgosLabs
//
//  Created by Krzysztof Gabis on 20.11.2013.
//  Copyright (c) 2013 Krzysztof Gabis. All rights reserved.
//

#include "colinear.h"

#include <math.h>
#include <vector>
#include <map>
#include <algorithm>
#include <math.h>

using std::vector;
using std::map;

struct vec2{
    double x,y;
    vec2 operator-(vec2 r) { return vec2(x-r.x, y-r.y); }
    vec2 operator+(vec2 r) { return vec2(x+r.x, y+r.y); }
    double operator%(vec2 r) { return x*r.x + y*r.y; }
    vec2() {}
    double operator^(vec2 r) { return x*r.y-y*r.x; }
    double length() { return sqrt(x*x + y*y); }
    vec2(double a,double b) { x=a; y=b; }
    vec2 inverse() { return vec2(-x, -y); }
    double theta() { return atan2(y, x); }
    bool isInLowerHalf() { return y < 0 || (y == 0 && x < 0); }
};

void load_points(vector<vec2> *points) {
    double x, y;
    FILE *fp = fopen("colinear.csv", "r");
    if (!fp) {
        puts("File not found!");
        return;
    }
    while(fscanf(fp, "%lf,%lf\n", &x, &y) != EOF) {
        points->push_back(vec2(x, y));
    }
    printf("Points count: %lu\n", points->size());
}

typedef map<double, int>::value_type map_vt;

int find_max_colinear(vector<vec2> &points) {
    int totalMax = 0;
    char buf[10];
    for (int i = 0; i < points.size(); i++) {
        map<double, int> thetaCountMap;
        vec2 &referencePoint = points[i];
        for (int j = 0; j < points.size(); j++) {
            if (i == j) {
                continue;
            }
            vec2 point = points[j];
            point = point - referencePoint;
            if (point.isInLowerHalf()) {
                point = point.inverse();
            }
            double theta = point.theta();
            if (theta == -0) theta = 0;
            double newTheta = 0;
            sprintf(buf, "%.4lf", theta);
            sscanf(buf, "%lf", &newTheta);
            thetaCountMap[newTheta] = thetaCountMap[newTheta] + 1;
        }
        int max = std::max_element(thetaCountMap.begin(),
                                   thetaCountMap.end(),
                                   [](map_vt &a, map_vt& b){ return a.second < b.second; })->second;
        totalMax = std::max(max, totalMax);
    }
    return totalMax + 1; // + 1 to account for point being tested
}

int main(int argc, const char **argv) {
    vector<vec2> points;
    load_points(&points);
    int max = find_max_colinear(points);
    printf("Max colinear: %d\n", max);
    return 0;
}

colinear.csv