Pages

Wednesday 16 January 2013

UVA - 270 - Lining Up

#include<stdio.h>
#include<string.h>
#define MAX 701

int coolinear(int x1,int y1,int x2,int y2,int x3,int y3){
    return (y1 - y2) * (x1 - x3) == (x1 - x2) * (y1 - y3);
}

int main()
{
    int i,ic,n ,j, z, counter, points,max;
    int x[MAX], y[MAX], arr[MAX][MAX], temp[MAX] ;
    char str[150];
    gets(str);
    sscanf(str, "%d", &n);
    gets(str);
    for(ic=0;ic<n;ic++){
        if(ic>0)
            printf("\n");
        points = 0;
        while(gets(str) != NULL){
            if(str[0] == '\0')
                break;
            sscanf(str, "%d%d", &x[points], &y[points]);
            points++;
        }
        memset(arr, -1, sizeof(arr));
        max = 0;
        for(i = 0; i < points; i ++)
            for(j = i + 1; j < points; j ++)
                if(arr[i][j]){
                    counter = 0;
                    for(z = 0; z < points; z++)
                        if(coolinear(x[i],y[i],x[j],y[j],x[z],y[z]))
                            temp[counter++] = z;
                    if(counter > max)
                        max = counter;
                    int l,m;
                    for(l = 0; l < counter; l ++)
                        for(m = l + 1; m < counter; m ++){
                            arr[temp[l]][temp[m]] = 0;
                            arr[temp[m]][temp[l]] = 0;
                        }
                }
        printf("%d\n", max);
    }
    return 0;
}

No comments:

Post a Comment