学步园

题目连接：http://zuojie.3322.org:88/soj/problem.action?id=4021

题目：

Description

You probably know what a set of collinear points is: a set of points such that there exists astraight line that passes through all of them. A set of cocircular points is defined in the samefashion, but instead of a straight line, we ask that there is a circle such that every point of theset lies over its perimeter.The International Collinear Points Centre (ICPC) has assigned you the following task: given aset of points, calculate the size of the larger subset of cocircular points.

Input

Each test case is given using several lines. The first line contains an integer N representing thenumber of points in the set (1 <= N <= 100). Each of the next N lines contains two integers Xand Y representing the coordinates of a point of the set (-10^4 <= X, Y <= 10^4). Within eachtest case, no two points have the same location.The last test case is followed by a line containing one zero.

Output

For each test case output a single line with a single integer representing the number of pointsin one of the largest subsets of the input that are cocircular.

Sample Input

7-10 00 -1010 00 10-20 10-10 20-2 44-10000 1000010000 1000010000 -10000-10000 -99993-1 00 01 00

Sample Output

532SourceLatin American Regional Contest 2010-->

直接枚举三个点，然后去计算圆心的方法是会超时的，标准的方法是去枚举两个点，然后在枚举第三个点，看构成的圆的圆心有多少重复再了一个地方。

通过统计这些次数我们便可以知道最多有多少个点共圆。

时间复杂度也就可以从O(n^4)降到了O(n^3logn)

虽然还是很高，但是适当的剪枝（比如枚举的时候只需要枚举一半左右的点）

还是可以过的。

我的代码：

#include<stdio.h>
#include<algorithm>
#include<math.h>
#define eps 1e-8

using namespace std;

struct node
{
	double x;
	double y;
};
struct line
{
	node a;
	node b;
};
node p[105];
int n;

bool cmp(node a,node b)
{
	if((a.x<b.x)||((fabs(a.x-b.x)<=eps)&&(a.y<b.y)))
		return true;
	return false;
}

double xmult(node p1,node p2,node p0)
{
	return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

bool judge_line(int a,int b,int c)
{
	double temp;
	temp=xmult(p[a],p[b],p[c]);
	if(fabs(temp)<=eps)
		return false;
	else
		return true;
}

node circle(node p1,node p2,node p3)
{
    node p;
    double a1=2*(p1.x-p2.x);
    double a2=2*(p1.x-p3.x);
    double b1=2*(p1.y-p2.y);
    double b2=2*(p1.y-p3.y);
    double c1=p1.x*p1.x+p1.y*p1.y-p2.x*p2.x-p2.y*p2.y;
    double c2=p1.x*p1.x+p1.y*p1.y-p3.x*p3.x-p3.y*p3.y;
    double t=a1*b2-a2*b1;
	p.x=(c1*b2-c2*b1)/t;
	p.y=(a1*c2-a2*c1)/t;
    return p;
}

int getans(int a,int b)
{
	int i,num=0,kkk=3,ret=0;
	double dis;
	node center[105];
	for(i=b+1;i<=n;i++)
	{
		if(judge_line(i,a,b))
			center[num++]=circle(p[a],p[b],p[i]);
	}
	if(num==0)
		return 2;
	sort(center,center+num,cmp);
	for(i=1;i<num;i++)
	{
		dis=(center[i-1].x-center[i].x)*(center[i-1].x-center[i].x)+(center[i-1].y-center[i].y)*(center[i-1].y-center[i].y);
		if(dis<=eps)
			kkk++;
		else
		{
			if(kkk>ret)
				ret=kkk;
			kkk=3;
		}
	}
	if(kkk>ret)
		ret=kkk;
	return ret;
}

int main()
{
	int i,j,temp,max;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)
			break;
		max=0;
		for(i=1;i<=n;i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		for(i=1;i<=n;i++)
			for(j=i+1;j<=n;j++)
			{
				temp=getans(i,j);
				if(temp>max)
					max=temp;
			}
		printf("%d\n",max);
	}
	return 0;
}