7_9_2013 A: Triangles-白红宇

7_9_2013 A: Triangles

阅读量：7038 次

发布时间：2019-06-28

本文共 2187 字，大约阅读时间需要 7 分钟。

Problem A: Triangles

Time Limit: 2 Sec

Memory Limit: 128 MB

Submit: 20

Solved: 9

[ ][ ][ ]

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 i-th 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.

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

這個題目一開始看沒有看懂題目，不明白爲什麽說明了點還要說明邊，就沒有去寫對我來說第二個難點就是不知道如何去實現邊關係的存儲，雖然以前寫過用二維數組實現邊關係的存儲，而這題有一點不同，在usc_w隊長的指導下，明白了要用map實現哈希對應如此來就是一道簡單的搜索題目了

#include 
    
     #include 
     
      #include 
      #include 
       
        #include 
        
         using namespace std;int n, m, sum;int edge[210][210];struct p{    double x, y;}point[210];map
         
          number;bool if_line(int i, int j, int k){ return fabs((point[j].x-point[i].x)*(point[k].y-point[j].y)- (point[k].x-point[j].x)*(point[j].y-point[i].y))<1e-8 ? true: false;}/*bool if_line(int i, int j, int k){ double xx1=point[j].x-point[i].x; double yy1=point[j].y-point[i].y; double xx2=point[k].x-point[j].x; double yy2=point[k].y-point[j].y; if(fabs(xx1*yy2-xx2*yy1)<1e-8) return true; return false;}*/voidslove(){ for(int i=0; i
          
           >n>>m){ sum=0; number.clear(); memset(edge, 0, sizeof(edge)); for(int i=0; i
           
            >point[i].x>>point[i].y; number[point[i].x*200000+point[i].y]=i; } for(int i=0; i
            
             >x1>>y1>>x2>>y2; int u=number[x1*200000+y1]; int v=number[x2*200000+y2]; edge[u][v]=edge[v][u]=1; } slove(); cout<
             
              <

转载于:https://my.oschina.net/dianpaopao/blog/143991

你可能感兴趣的文章