周日起床后看见QQ群消息说 bupt上有半同步北京现场赛试题,就进入看了下题,一共读了两个题 A和B(因为这两个题目当时就都提交的很多)
A题不会做,有限制的生成树的这类知识好像还没有接触过。。。
B题 感觉数据非常小,觉得暴力枚举也能过 就试着写了下 提交几次后竟然过了 嘿嘿
B题题意大致是 给你多个点,让任意三个点可以组合三角形的构成三角形,并把这些三角形分成N个集合,每个集合内的三角形 两两相似,问最大的一个集合有多少个三角形。我的写法 是以此枚举三个点看能否够成三角形,如果能构成三角形 就先把三角存起来,继续枚举。。。 最后拿每一个三角形和所有的三角形比较看是否相似,记录相似个数,输出最大一个数就可以了(一句话概括就是输入n个点,求最多的相似三角形个数)
主要有三点需要注意:一是输入点时记得去重 二是判断共线的 不能用斜率相等,因为有斜率不存在的情况, 三是精度,double不能用==判断是否相等
下面是我的代码
#include<cstdio>#include<cstring>#include<cmath>#include<iostream>using namespace std;double a[20],b[20];double v[900][3];int zero(double a,double b){if(a-b<0.000001&&a-b>-0.000001) return 1;if(b-a<0.000001&&b-a>-0.000001) return 1;return 0;}int main(){int n,m,i,j,k,N;while(scanf("%d",&n)&&n){N=0;memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(v,0,sizeof(v));for(i=0;i<n;i++){scanf("%lf%lf",&a[i],&b[i]);for(j=0;j<N;j++)if(a[i]==a[j]&&b[i]==b[j]) break;if(j==N) { a[N]=a[i]; b[N]=b[i]; N++;}}m=0;for(i=0;i<N;i++)for(j=0;j<i;j++)for(k=0;k<j;k++)if(!zero((a[k]-a[j])*(b[j]-b[i]),(a[j]-a[i])*(b[k]-b[j]))){v[m][0] = sqrt( (a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j]) );v[m][1] = sqrt( (a[j]-a[k])*(a[j]-a[k])+(b[j]-b[k])*(b[j]-b[k]) );v[m][2] = sqrt( (a[k]-a[i])*(a[k]-a[i])+(b[k]-b[i])*(b[k]-b[i]) );m++;}int num,max=0;for(i=0;i<m;i++)for(num=0,j=0;j<m;j++)if( zero(v[i][0]/v[j][0],v[i][1]/v[j][1]) && zero(v[i][2]/v[j][2],v[i][1]/v[j][1]) ) num++;else if( zero(v[i][0]/v[j][0],v[i][1]/v[j][2]) && zero(v[i][2]/v[j][1],v[i][1]/v[j][2]) ) num++; else if( zero(v[i][0]/v[j][1],v[i][1]/v[j][0]) && zero(v[i][2]/v[j][2],v[i][1]/v[j][0]) ) num++; else if( zero(v[i][0]/v[j][1],v[i][1]/v[j][2]) && zero(v[i][2]/v[j][0],v[i][1]/v[j][2]) ) num++; else if( zero(v[i][0]/v[j][2],v[i][1]/v[j][1]) && zero(v[i][2]/v[j][0],v[i][1]/v[j][1]) ) num++;else if( zero(v[i][0]/v[j][2],v[i][1]/v[j][0]) && zero(v[i][2]/v[j][1],v[i][1]/v[j][0]) ) num++; if(num>max) max=num;printf("%d\n",max);}}