xmu1341 共圆四边形

//题目链接：http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1341


//题意：YT喜欢四边形，尤其是四点共圆的四边形。
//现在YT想问问大家，给你N个点，会组成多少个四点共圆四边形呢。

//PS:这一道厦大校赛几何题，我泪奔了好几天，O.O

//解题思路：
//首先想到的当然n^4地暴力果断T回来，然后再想枚举3个点，再3个for循环中去找相同点，又被T回来。
//只是想过记录每个内接三角形怕数组过大，导致排序超时，没想到这个也可以（内心不够强大啊），
//在排序过程中，用sqort竞出错了，无耐只好用sort，到现在还不是很明白sqort错在哪了。


//排完序后找出m个点所组成的C[3,m]个内接三角形（C[3,m]可遍历得到），
//就有C[4,m]个四边形，我只好记录一下C[3,m]与m的关系，求出m。再对C[3,m]*(m-3)/4;

//11308K 1580MS AC还不是很快,仰慕还不到1000MS的大神。代码如下：

#include<iostream>         
#include<cstdio>         
#include<math.h>         
#include<map>      
#include<algorithm>
#define eps 1e-8        

struct point{double x,y;};         
struct line{point a,b;};         

int distance(point p1,point p2){         
    return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);         
}         

bool zero(double x)         
{         
    return x>0.0? x<eps: x>-eps;         
}         


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

point intersection(line u,line v){         
    point ret=u.a;         
    double t=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))         
        /((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));         
    ret.x+=(u.b.x-u.a.x)*t;         
    ret.y+=(u.b.y-u.a.y)*t;         
    return ret;         
}         

//外心         
point circumcenter(point a,point b,point c){         
    line u,v;         
    u.a.x=(a.x+b.x)/2.0;         
    u.a.y=(a.y+b.y)/2.0;         
    u.b.x=u.a.x-a.y+b.y;         
    u.b.y=u.a.y+a.x-b.x;         
    v.a.x=(a.x+c.x)/2.0;         
    v.a.y=(a.y+c.y)/2.0;         
    v.b.x=v.a.x-a.y+c.y;         
    v.b.y=v.a.y+a.x-c.x;         
    return intersection(u,v);         
}         

point p[160];         
struct Node      
{      
    double x,y;      
    int r;      
	//   int num;      
}; 
struct Node node[4000000] ;   
bool cmp2(const Node &a,const Node &b)
{
	if(a.r==b.r)
	{
		if(zero(a.x-b.x))return a.y>b.y;
		else return a.x>b.x;
	}
	else return a.r>b.r;
}

int g[1000000];      
void init()
{
	int i;  
	for(i=3;i<150;i++)      
	{      
		int temp=i*(i-1)*(i-2)/6;      
		g[temp]=i;      
	}      
}
int main()         
{  
	int n,i,j,k,h;        
	init();
	int cas;         
	scanf("%d",&cas);         
	while(cas--)         
	{         
		scanf("%d",&n);         
		for(i=0;i<n;i++)         
			scanf("%lf%lf",&p[i].x,&p[i].y);         
		int index=0;
		for(i=0;i<n;i++)         
		{         
			for(j=i+1;j<n;j++)         
			{         
				for(k=j+1;k<n;k++)         
					if(!zero(xmult(p[i],p[j],p[k])))         
					{   
						point cen=circumcenter(p[i],p[j],p[k]);
						int dis=distance(cen,p[i]);      
						node[index].x=cen.x;  
						node[index].y=cen.y;
						node[index].r=dis; 
						index+=1;
					}         
			}         
		}         
		// qsort(node,index,sizeof(node[0]),cmp);
		std::sort(node,node+index,cmp2);
		int cnt=0;   
		int num=1;
		for(i=1;i<index;i++)      
		{       
			if(zero(node[i].r-node[i-1].r)
				&&zero(node[i].x-node[i-1].x)
				&&zero(node[i].y-node[i-1].y))
			{
				num+=1;
			}
			else
			{
				if(num>3) cnt+=num*(g[num]-3)/4;
				num=1;
			}
		}      
		if(num>3) cnt+=num*(g[num]-3)/4;
		printf("%d\n",cnt);         
	}         
	return 0;         
}