Triangles Time Limit: 1 Sec Memory Limit: 128 MB Submissions: 115 Solved: 30 Description You are given a figure consisting of n points in a 2D-plane and m segments connecting some of them. We guarantee that any two segments don't share points except their ends and there's no more than one segment between the same pair of points. Please count the total number of triangles in the given figure. Input There're multiple test cases. In each case: The first line contains two positive integers n and m. (n <= 200, m <= 20000) Each of the following n lines contains two real numbers xi and yi indicating the coordinates of the ith point. (-100000 < xi, yi < 100000) Each of the following m lines contains four real numbers xi, yi, xj , yj . It means (xi, yi) and (xj , yj) are connected by a segment. We guarantee that these points are part of the given n points. Output For each test case, print a single line contains the total number of triangles in the given figure. Please see sample for more details Sample Input 4 5 0 0 1 1 2 0 1 0 0 0 1 1 1 1 2 0 2 0 1 0 1 0 0 0 1 1 1 0 Sample Output 3 HINT Source The 7th(2012) ACM Programming Contest of HUST Problem Setter: Zhou Zhou 下面的都是抄襲大神的 莫要鄙視 額先保存下 感覺這個題很好 有必要保存下 題意：給一些點的坐標和裡面的點構成的一些線段，求這些線段可以構成多少個三角形； 思路：因為的點的個數只有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)，具體看 下面是大神的代碼 [cpp] #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; }
