题意：给出一定的点，然后再给出哪些点相连，问最后这些相连点的组成多少个三角形，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; }