POJ 1118 Lining Up（我的水題之路——斜率最多）

這道題看上去感覺像是幾何題，題中給了最多700個點，讓你求出這700個點中最多有多少個共線。

由于資料量比較少就選擇用暴力過，

對于每一個點，對于其他所有點進行求斜率，将所有的斜率存在一個數組中，之後對這個數組進行排序，排序之後，對于相鄰的兩個斜率進行比較，如果兩個斜率相同，就讓共點數+1.求出共點數的最大值。

注意兩點：

1、該題的共點數最小為2，因為至少有兩個點共線，這一點讓我WA了很久！T_T

2、如果，兩個點的橫坐标相同，則其斜率為無窮大，就定義為一個比較大的常數32767

代碼：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

int aid[1000][2];
float xielv[1000];

int main(void){
    int i, j, k;
    int max, tmp;
    int n;

    while (scanf("%d", &n), n != 0){
        memset(aid, 0, sizeof(aid));
        for (i = 0; i < n; i++){
            scanf("%d%d", &aid[i][0], &aid[i][1]);
        }
        max = 2;
        for (i = 0; i < n - 1; i++){
            for (j = i + 1, k = 0; j < n; j++){
                if (aid[j][0] == aid[i][0]){
                    xielv[k++] = 32767;
                }
                else{
                    xielv[k++] = (float)(aid[j][1] - aid[i][1]) / (float)(aid[j][0] - aid[i][0]);
                }
            }
            sort(xielv, xielv + k);
            for (j = 1, tmp = 2; j <= k; j++){
                if (xielv[j] == xielv[j - 1]){
                    tmp ++;
                    if (tmp > max){
                        max = tmp;
                    }
                }
                else{
                    tmp = 2;
                }
            }
        }
        printf("%d\n", max);
    }
    return 0;
}