Planet Communcation Gym - 101466C （模拟+GCD）

　Lately the communication between planets has been an important issue, which is why the Earth has made many efforts to be connected to every other planet in the universe.

　The Universal Network Army of Lasers (UNAL) is trying to connect the Earth with other planets in the universe. In order to make this, the UNAL uses a laser machine which each time it is used, it sends a communication signal in the form of a ray of light in the direction of the planet.

　This laser machine is so powerful, that a ray of light generated by it is capable to cross all the planets it touches until the end of the universe. Moreover, when it fires a ray of light in one direction it also fires a ray of light in the opposite direction.

　Given the coordinates of all the planets in the universe, help the UNAL to design the way to communicate the Earth with all other planets in the universe using the machine the minimum number of times.

 

Input

　The first line of input contains one integer n (1 ≤ n ≤ 5000), the number of planets.

　The next n lines contains the list of coordinates of the planets. In particular, the i - th line contains three integers x_i, y_i, z_i ( - 10⁹ ≤ x_i, y_i, z_i ≤ 10⁹), the coordinates of the i - th planet, respectively. The Earth is the first planet on the list. It is guaranteed that all the planets have different coordinates.

 

Output

　Output a single integer, the minimun number of times the machine should be used to communicate the Earth with all other planets in the universe

 

Examples

Input

3
0 0 0
1 1 0
-1 -1 0

Output

1

Input

4
0 0 0
1 0 0
0 1 0
0 0 1

Output

3

  题意： 在三维空间给n个坐标，第一个坐标是地球的，问地球想对其他n-1个星球发射信号，最少需要发射多少个 说白了就是问n-1个星球与地球分别连线，求共线的有几条，总数减去共线的就是最少个数   思路： 用gcd将坐标化简，看有多少重复的，减掉就可以了 GCD，欧几里得算法，也称辗转相除法，用来求最大公倍数的不二算法  

  1 #include <stdio.h>
  2 #include <string.h>
  3 
  4 struct node
  5 {
  6     long long a, b, c;
  7 } str[5005];
  8 
  9 long long vis[5005];
 10 
 11 long long gcd(long long a, long long b)   //低调奢华有内涵的gcd
 12 {
 13     if(b==0) return a;
 14     else return gcd(b, a%b);
 15 }
 16 
 17 int main()
 18 {
 19     long long n, i, j, x, m;
 20     long long a, b, c, eara, earb, earc;
 21     m = 0;
 22     scanf("%lld", &n);
 23     memset(vis, 0, sizeof(vis));
 24     scanf("%lld %lld %lld", &eara, &earb, &earc);   //地球坐标
 25     n--;   //除去地球，n-1颗星球
 26     for(i=0; i<n; i++)
 27     {
 28         scanf("%lld %lld %lld", &a, &b, &c);
 29 
 30         a -= sa;   //相对地球的坐标
 31         b -= sb;
 32         c -= sc;
 33 
 34         if(a<0)     //反向也是共线，为了以后数据处理的方便，变个号，统一起来
 35         {
 36             a = -a;
 37             b = -b;
 38             c = -c;
 39         }
 40         if(a==0&&b==0)     //大粗长判断为的就是拿到最简坐标，0特殊考虑
 41         {
 42             str[i].a = str[i].b = 0;
 43             str[i].c = 1;
 44         }
 45         else if(b==0&&c==0)
 46         {
 47             str[i].b = str[i].c = 0;
 48             str[i].a = 1;
 49         }
 50         else if(a==0&&c==0)
 51         {
 52             str[i].a = str[i].c = 0;
 53             str[i].b = 1;
 54         }
 55         else if(a==0)
 56         {
 57             str[i].a = 0;
 58             x = gcd(b, c);
 59             str[i].b = b / x;
 60             str[i].c = c / x;
 61         }
 62         else if(b==0)
 63         {
 64             str[i].b = 0;
 65             x = gcd(a, c);
 66             str[i].a = a / x;
 67             str[i].c = c / x;
 68         }
 69         else if(c==0)
 70         {
 71             str[i].c = 0;
 72             x = gcd(a, b);
 73             str[i].a = a / x;
 74             str[i].b = b / x;
 75         }
 76         else
 77         {
 78             x = gcd(a, gcd(b, c));
 79             str[i].a = a/x;
 80             str[i].b = b/x;
 81             str[i].c = c/x;
 82         }
 83         
 84     }
 85 
 86     for(i=0; i<n; i++)    //看看最简坐标有多少重复出现的（即共线）
 87     {
 88         if(vis[i]==1) continue;    //vis为1是已经判断过的，对于这种思路来讲不写会答案错误
 89         vis[i] = 1;
 90         for(j=i; j<n; j++)
 91         {
 92             if(str[i].a==str[j].a&&str[i].b==str[j].b&&str[i].c==str[j].c&&vis[j]==0)
 93             {
 94                 vis[j] = 1;
 95                 m++;
 96             }
 97         }
 98     }
 99     
100     printf("%lld\n", n-m);
101     return 0;
102 }