水平線分と垂直線分の三角形の数を見つけるC++プログラム

この記事では、指定された水平線分と垂直線分の交点を結合することによって形成できる三角形の数を見つけるプログラムについて説明します。

たとえば、次の線分が与えられたとしましょう。これには3つの交点があります。したがって、これらの点を使用して形成できる三角形の数は ³ になります。 C ₂ 。

   |
---|--------|--
   |        |
   |  --|---|
   |        |

スイープラインアルゴリズムに従います。線分のすべての値を保存し、一方の線の内側の点が他の線の内部の点とも比較されるかどうかを確認します。このようにして、指定された線分のすべての交点を取得し、さまざまな可能な組み合わせを使用して、可能な三角形の数を簡単に見つけることができます。

例

#include<bits/stdc++.h>
#define maxy 1000005
#define maxn 10005
using namespace std;
//to store intersection points
struct i_point {
   int x, y;
   i_point(int a, int b) {
      x = a, y = b;
   }
};
int bit[maxy];
vector < pair <i_point, int> > events;
//to sort the given points
bool com_points(pair<i_point, int> &a, pair<i_point, int> &b) {
   if ( a.first.x != b.first.x )
      return a.first.x < b.first.x;
   else {
      if (a.second == 3 && b.second == 3) {
         return true;
      }
      else if (a.second == 1 && b.second == 3) {
         return true;
      }
      else if (a.second == 3 && b.second == 1) {
         return false;
      }
      else if (a.second == 2 && b.second == 3) {
         return false;
      }
      return true;
   }
}
void topdate_line(int index, int value) {
   while (index < maxn) {
      bit[index] += value;
      index += index & (-index);
   }
}
int query(int index) {
   int res = 0;
   while (index > 0) {
      res += bit[index];
      index -= index & (-index);
   }
   return res;
}
//to insert a line segment
void insertLine(i_point a, i_point b) {
   //in case of horizontal line
   if (a.y == b.y) {
      int begin = min(a.x, b.x);
      int end = max(a.x, b.x);
      events.push_back(make_pair(i_point(begin, a.y), 1));
      events.push_back(make_pair(i_point(end, a.y), 2));
   }
   //in case of vertical line
   else {
      int top = max(b.y, a.y);
      int bottom = min(b.y, a.y);
      events.push_back(make_pair(i_point(a.x, top), 3));
      events.push_back(make_pair(i_point(a.x, bottom), 3));
   }
}
//to calculate number of intersection points
int calc_i_points() {
   int i_points = 0;
   for (int i = 0 ; i < events.size() ; i++) {
      if (events[i].second == 1) {
         topdate_line(events[i].first.y, 1);
      }
      else if (events[i].second == 2) {
         topdate_line(events[i].first.y, -1);
      }
      else {
         int bottom = events[i++].first.y;
         int top = events[i].first.y;
         i_points += query(top) - query(bottom);
      }
   }
   return i_points;
}
int calc_triangles() {
   int points = calc_i_points();
   if ( points >= 3 )
      return ( points * (points - 1) * (points - 2) ) / 6;
   else
      return 0;
}
int main() {
   insertLine(i_point(3, 2), i_point(3, 13));
   insertLine(i_point(1, 5), i_point(3, 5));
   insertLine(i_point(8, 2), i_point(8, 8));
   insertLine(i_point(3, 4), i_point(6, 4));
   insertLine(i_point(4, 3), i_point(4, 5));
   sort(events.begin(), events.end(), com_points);
   cout << "Possible number of triangles : " << calc_triangles() << endl;
   return 0;
}

出力

Possible number of triangles : 1