uva - 270 - Lining Up（枚舉、排序）

題意：輸入幾個點，輸出最多有幾個點在一條直線上。

方法：枚舉所有點與其他點的斜率，取斜率相同最多的情況。時間復雜度O（n^n）。

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   

using namespace std;

#define MAX 700+10
struct Point
{
	int x;
	int y;
};

int n, _max = 2;
Point point[MAX];
double slope[300000];

void Input()
{
	char s[100];
	int k = 0;
	while (gets(s) != NULL && s[0] != '\0')
	{
		char  temp_1[100], temp_2[100];
		memset(temp_1, 0, sizeof(temp_1));
		memset(temp_2, 0, sizeof(temp_2));
		int i = 0, j = 0;
		for (i = 0; s[i] != ' '; i++)
			temp_1[j++] = s[i];
		for (i++, j = 0; i < strlen(s); i++)
			temp_2[j++] = s[i];
		point[n].x = atoi(temp_1);
		point[n].y = atoi(temp_2);
		n++;
	}
}

double Cal_Slope(Point a, Point b)
{
	return (double)(b.y - a.y)/(b.x - a.x);
}

int cmp(const void *a, const void *b)
{
	return *(double *)a > *(double *)b ? 1 : -1;
}

void Search(int k)
{
	int i = 0, count = 2;
	for (i = 1; i < k; i++)
	{
		if (slope[i] - slope[i-1] < 1e-10)
		{
			count++;
			if (count > _max)
				_max = count;
		}
		else
			count = 2;
	}
}

int main()
{
#ifdef Local  
	freopen("a.in", "r", stdin);  
#endif  
	int t = 0, i = 0, j = 0, k = 0;
	cin >> t;
	getchar(), getchar();
	while (t--)
	{
		memset(slope, 0, sizeof(slope));
		memset(point, 0, sizeof(point));
		_max = 2, n = 0;
		Input();
		if (2 == n)
			cout << "2" << endl;
		else
		{
			for (i = 0; i < n-1; i++)
			{
				k = 0;
				for (j = 0; j < n; j++)
					if(j != i)
						slope[k++] = Cal_Slope(point[i], point[j]);
				qsort(slope, k, sizeof(slope[0]), cmp);
				Search(k);
			}
			cout << _max << endl;
		}
		if (t)
			cout << endl;
	}
}

輸出最小為2，WA在寫成0了，第一次WA是把所有的斜率都列出來排序，錯誤！