题意:给出一定的点,然后再给出哪些点相连,问最后这些相连点的组成多少个三角形,hash的应用
分析:转载牛人的思想
题意:给一些点的坐标和里面的点构成的一些线段,求这些线段可以构成多少个三角形;
思路:因为的点的个数只有100,所以枚举三个点就可以了,O(n^3);
只不过这里有一些条件:这三个点构成的三条线段必须在前面给的线段里,怎么判断呢?
这里我们可以用hash坐标的方法,把一个点的坐标hash成一个数字,这个很简单,就是把
每个点的x,y坐标加上100000,最后key=x*200000+y,因为y不会超过200000,所以
这样就可以保证每个点的坐标不相同了,然后我们再把key和坐标的序号建立一个映射就好了;
再然后我们可以为100点建立一个邻接矩阵,开始输入数据的时候,每来一个线段,我们找到
线段两端的坐标得到它的hash值,并用映射关系找到这个点的序号,然后把邻接矩阵里两个序
号对应的位置赋值为1,例如现在线段两个端点的序号是1和2,map[][]为链接矩阵,那么我们
就令map[1][2]=map[2][1]=1,像加了一条边一样,这样我们就得到了所有点与点之间的关系了;
接下来我们还要解决一个问题,比如线段ab和bc平行,那么我们就又可以得到一条新的线段也就是ac,
解决这个问题我们可以用点疏松的方法,这个类似于floyd算法,时间复杂度O(n^3),具体看
下面是大神的代码
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<map>
using namespace std;
struct node {double x,y;};
node point[220];
double yy[220];
map <double,int > pp ;
double get(double x,double y) //点hash
{
// x+=100000;
// y+=100000;
x*=200000;
x+=y;
return x;
}
int mp[220][220];
double dis(node a,node b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int judgeline(node a,node b,node c)//判断线段共线 注意垂直的时候斜率为0 要单独判断啊
{
double x,y,z,t;
x=a.x-c.x;
y=a.y-c.y;
z=b.x-c.x;
t=b.y-c.y;
if((t<1e-8&&t>-1e-8)&&(y<1e-8&&y>-1e-8))return 1;
else
{
if((t<1e-8&&t>-1e-8)||(y<1e-8&&y>-1e-8))return 0;
t=(x/y)-(z/t);
return (t<1e-8&&t>-1e-8);
}
}
int subjudge(node a,node b,node c)//判断三角形
{
double x,y,z;
x=dis(a,b);
y=dis(a,c);
z=dis(b,c);
if(x+y-z>1e-8&&x+z-y>1e-8&&y+z-x>1e-8)
return 1;
else return 0;
}
int judge(int a,int b,int c) //判断3个点的关系是否满足
{
if(mp[a][b]&&mp[a][c]&&mp[b][c])
return subjudge(point[a],point[b],point[c]);
else return 0;
}
int main()
{
int n,m,a,b,i,j,k,sum;
double x1,y1,x2,y2;
while(scanf("%d%d",&n,&m)!=EOF)
{
pp.clear();//这里清零很重要不要再忘记了
for(i=0;i<n;i++)
{
scanf("%lf%lf",&point[i].x,&point[i].y);
yy[i]=get(point[i].x,point[i].y); //点hash
pp[yy[i]]=i; //点与序号的映射
}
memset(mp,0,sizeof(mp));
for(i=0;i<m;i++) //建立邻接矩阵
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
a=pp[get(x1,y1)];
b=pp[get(x2,y2)];
mp[a][b]=1;
mp[b][a]=1;
}
for(i=0;i<n;i++) //点疏松
{
for(j=0;j<n;j++)
{
if(i!=j)
{
for(k=0;k<n;k++)
{
if(i!=k&&i!=j&&j!=k)
{
if(!mp[j][k]&&mp[i][j]&&mp[i][k]&&judgeline(point[i],point[j],point[k]))
mp[j][k]=1,mp[k][j]=1;
}
}
}
}
}
sum=0;
for(i=0;i<n;i++) //三角形枚举并判断
for(j=i+1;j<n;j++)
for(k=j+1;k<n;k++)
sum+=judge(i,j,k);
printf("%d\n",sum);
}
return 0;
}