11227 - The silver bullet

easy.cpp

#include <stdio.h>
#include <algorithm>
#include <stdlib.h>  
#include <iostream>
#include <cstdlib>
  
using namespace std;  
  
const int MAX = 120;  
struct position {double x,y;};  
position positions[MAX];  
  
double crossProduct(position a,position b,position c)  
{  
    return (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y);  
}  
bool cmp( position a,position b)  
{  
    if( a.x == b.x ) return a.y < b.y;  
    return a.x < b.x;  
}  
bool equal_cmp(position a, position b)  
{  
    return a.x == b.x && a.y == b.y;  
}  
  
int main()  
{  
    int testCases;
    int number_of_positions;
    int data_set_number = 1;
    int answer = 0; 
    int sum=0;
      
    cin >> testCases;  
      
    while(testCases > 1)
    {  
        cin >> number_of_positions;
        int i=0,j=0,k,l;
        for(i=0; i<number_of_positions; i++){
            cin >> positions[i].x;
            cin >> positions[i].y;
        }
        sort(positions, positions+number_of_positions, cmp);
        number_of_positions = unique(positions, positions+number_of_positions, equal_cmp) - positions;  
        cout << "Data set #" << data_set_number << " contains ";  
        data_set_number++;
        if( number_of_positions == 1 )  
        {  
            cout << "a single gnu." << endl;  
            continue;  
        }  
         
        for(i=0; i<number_of_positions; i++)  
            for(k=i+1; k<number_of_positions; k++)  
            {  
                sum = 2;  
                for(l=k+1; l<number_of_positions; l++) {
                    if( crossProduct(positions[i], positions[k], positions[l]) == 0){ 
                        sum++;
                    }
                }
                if(sum > answer){
                    answer = sum;  
                }
            }         
        cout << number_of_positions << " gnus, out of which a maximum of " << answer << " are aligned." << endl; 
        testCases--;
    }  
  
return 0;  
}