首页 > 代码库 > FZU2111

FZU2111

在平面上给你N个点,找出有几个锐角三角形。做法简单,先求出所有三角形个数(c n3)。开三个for循环,搜索所有三角形,是钝角或直角就减一。直接上代码吧。

#include <stdio.h>
#include <math.h>
int main()
{
	__int64 n,i,j,k,sum,sum1,sum2;
	double a[5000],b[5000];
	scanf("%I64d",&n);
	while(n--)
	{
		__int64 m;
		sum=1;
		sum1=1;
		scanf("%I64d",&m);
        for(i=m,j=3;j>0;j--,i--)
		{
			sum*=i;
			sum1*=j;
		}
		sum2=sum/sum1;
		for(i=1;i<=m;i++)
			scanf("%lf%lf",&a[i],&b[i]);
		for(i=1;i<=m-2;i++)
			for(j=i+1;j<=m-1;j++)
				for(k=j+1;k<=m;k++)
				{
					if((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j])>=(a[i]-a[k])*(a[i]-a[k])+(b[i]-b[k])*(b[i]-b[k])+(a[j]-a[k])*(a[j]-a[k])+(b[j]-b[k])*(b[j]-b[k]))
						sum2--;
					if((a[i]-a[k])*(a[i]-a[k])+(b[i]-b[k])*(b[i]-b[k])>=(a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j])+(a[j]-a[k])*(a[j]-a[k])+(b[j]-b[k])*(b[j]-b[k]))
						sum2--;
					if((a[j]-a[k])*(a[j]-a[k])+(b[j]-b[k])*(b[j]-b[k])>=(a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j])+(a[i]-a[k])*(a[i]-a[k])+(b[i]-b[k])*(b[i]-b[k]))
						sum2--;
				}
				printf("%I64d\n",sum2);		
	}
	return 0;
}


 

FZU2111