图中有多少个三角形

54 阅读 0 评论 36 点赞

我是靠谱客的博主勤恳导师，最近开发中收集的这篇文章主要介绍图中有多少个三角形，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：编程计算下面图形中包含多少个三角形。

思路：首先给图中每个线段的交点设一个字母标记，不是任何两个字母都构成一条线段，使用穷举法列出所有线段；

之后将图中所有的线段进行任意3条的组合，如果这3条线段能构成一个三角形，则计数加一，否则计数不变。

判断线段能否组成三角形，需要注意每两条线段之间是否有交点、三条线段是否共线、三条线段是否有同一交点。

#include "stdio.h"

#define NO_POINT '0'

char * map[] = {"ab","ad","db","ag","gc","ac","ah","ae","ej","jh",
"aj","eh","af","ak","ai","fk","fi","ki","de","df","dg","ef","eg",
"fg","bj","bk","bg","jk","jg","kg","bh","bi","bc","hi","hc","ic"};

char *line[] = {"adb","agc","aejh","afki","defg","bjkg","bhic"};

int contains(char *str, char a) {
   int i = 0;
   while (str[i] != 0) {
       if (str[i] == a) {
           return 1;
       }
       i++;
   }
   return 0;
}

int isInALine(char a, char b, char c) {
   int i=0;
       for (i = 0; i<7; i++) {
           if (contains(line[i],a) == 1
               && contains(line[i],b) == 1
               && contains(line[i],c) == 1) {
               return 1;
           }
       }
       return 0;
}
char getCrossPoint(char * s1, char *s2) {
   if (*s1 == *s2 ) {
       return *s1;
   }
   if (*s1 == *(s2+1)) {
       return *s1;
   }
   if (*(s1+1) == *s2) {
       return *s2;
   }
   if (*(s1+1) == *(s2+1)) {
       return *(s1+1);
   }

return NO_POINT;
}

int isTriangle(char * str1, char *str2, char * str3) {
   char p1, p2, p3;
   p1 = getCrossPoint(str1, str2);
   if (p1 == NO_POINT) return 0;
   p2 = getCrossPoint(str2, str3);
   if (p2 == NO_POINT) return 0;
   p3 = getCrossPoint(str1, str3);
   if (p3 == NO_POINT) return 0;

   if (p1 != p2 && p2 != p3 && p1 != p3
       && isInALine(p1,p2,p3) == 0) {
       //printf("(%c,%c,%c)",p1,p2,p3);
       return 1;
   }
   return 0;
}

int getTriangleCount() {
int i, j, k;
int count = 0;

   for (i=0; i<36; i++) {
       for (j=i+1; j<36; j++) {
           for (k=j+1; k<36; k++) {
               if (isTriangle(map[i], map[j], map[k])) {
                   count++;
               }
           }
       }
   }

return count;
}

main() {
printf("It contains %d trianglen", getTriangleCount());
getchar();
}