Source Code

Problem: 1118  User: dawei007 
Memory: 160K  Time: 94MS 
Language: C++  Result: Accepted 

Source Code 
#include<stdio.h>
#include <algorithm> 
using namespace std;
struct POS
{
	int x,y;
};
struct name_compare
{
	bool operator()(const POS& a, const POS& b) const
	{ return a.x<b.x; }
};
int main()
{
	int i,j,n;
	POS p[700];

	while(scanf("%d",&n))
	{
		if(n==0)
			break;

		int max1=0,t=0;
		int max2=0;

		for(i=0;i<n;i++)
		{
			scanf("%d %d",&p[i].x,&p[i].y);
		}
		sort(p, p+n, name_compare());

		for(i=0;i<n-1;i++)
		{
			t=1;
			while(p[i].x==p[i+1].x)
			{	++i;++t;	}
			if(t>max1)
				max1=t;
		}
		double slope[700];
		for(i=0;i<n;i++)
		{
			int pos=0;
			for(j=i;j<n;j++)//在这优化下（因为无论如何，那条斜率的已经算过了）
			{
				if(i!=j && p[i].x!=p[j].x)
					slope[pos++] = ( p[i].y-p[j].y )*1.0/(p[i].x-p[j].x);
			}
			sort(slope,slope+pos);
			int max=0;
			for(j=0;j<n-1;j++)
			{
				t=1;
				while(slope[j]==slope[j+1])
				{	++j;++t;	}
				if(t>max)
					max=t;
			}
			++max;
			if(max>max2)
				max2=max;
		}
		printf("%d\n",max1>max2?max1:max2);
	}
	return 0;
}

• 其实你还有一处算是优化了的 (25) rtest 2011-04-19 22:10:36
• Re:优化下 Time: 94MS 不知c32ms如何做的，知道的告诉下 (66) dengdai68 2012-02-25 18:17:19
• 你的程序有问题 (66) dengdai68 2012-02-25 18:18:02