poj 1118 Lining Up【同一条直线上的点】

这道题总算没有让我感觉超级水，至少我还超时了一次。。。哈哈哈

题意还比较容易懂：给出 n 个点的整数坐标（n<=700），求一条直线，使得在这条直线上的点数最多，输出点数。

解题思路：采用几何中的三个点是否在一条直线上判定定理：(yi-yk)/(xi-xk)=(yj-yk)/(xj-xk)，除法不能出现分母为0的情况，所以转换为乘法做（而且乘法效率也高些），即：(y[i]-y[k])*(x[j]-x[k])==(y[j]-y[k])*(x[i]-x[k])（i、j、k共线）。

暴搜肯定尽量追求不重不漏，重了会超时（因为三重循环重复count，我就超了一次），漏了必然WA。。。

另外我发现OJ上可以在循环里面定义变量

超时的代码：

#include <stdio.h>

int x[702],y[702];

int main()
{
	int n;

	int i;
	while(scanf("%d",&n))
	{
		if(n==0)
			return 0;

		//输入坐标点的值
		for(i=1;i<=n;i++)
			scanf("%d%d",&x[i],&y[i]);

		//暴搜开始
		int count,max=-1;
		int j,k;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
				if(j==i)
					continue;

                count=2;
                for(k=1;k<=n;k++)
				{
					if(k==i || k==j)
						continue;

					if((y[i]-y[k])*(x[j]-x[k])==(y[j]-y[k])*(x[i]-x[k]))
						count++;
				}

                if(max<count) max=count;
            }

		printf("%d\n",max);
	}

	return 0;
}

后来改进，AC的代码：

#include <stdio.h>

int x[702],y[702];

int main()
{
	int n;

	int i;
	while(scanf("%d",&n))
	{
		if(n==0)
			return 0;

		//输入坐标点的值
		for(i=1;i<=n;i++)
			scanf("%d%d",&x[i],&y[i]);

		//暴搜开始
		int count,max=-1;
		int j,k;
        for(i=1;i<=n;i++)
            for(j=i+1;j<=n;j++)
            {
                count=2;
                for(k=j+1;k<=n;k++)
                    if((y[i]-y[k])*(x[j]-x[k])==(y[j]-y[k])*(x[i]-x[k])) count++;

                if(max<count) max=count;
            }

		printf("%d\n",max);
	}

	return 0;
}