fork(2) download
  1. #include <map>
  2. #include <set>
  3. #include <vector>
  4. #include <memory>
  5. #include <cmath>
  6. #include <cstdio>
  7.  
  8. using namespace std;
  9.  
  10. struct point;
  11.  
  12. int gcd(int a, int b) {
  13. if (a < 0) a = -a;
  14. if (b < 0) b = -b;
  15. if (a < b) swap(a, b);
  16. while (b != 0) {
  17. int c = a % b;
  18. a = b;
  19. b = c;
  20. }
  21. return a;
  22. }
  23.  
  24. struct edge_coordinate {
  25. int a, b;
  26.  
  27. edge_coordinate(int x, int y, int d) {
  28. int aa = 5*x + d*y;
  29. int bb = 5*y - d*x;
  30. int g = gcd(aa, bb);
  31. a = aa/g;
  32. b = bb/g;
  33. }
  34. bool operator<(const edge_coordinate& other) const {
  35. return (a != other.a) ? (a < other.a) : (b < other.b);
  36. }
  37. bool operator==(const edge_coordinate& other) const {
  38. return (a == other.a) && (b == other.b);
  39. }
  40. };
  41.  
  42. struct edge {
  43. edge_coordinate coordinate;
  44. set<point*> pts1;
  45. set<point*> pts2;
  46.  
  47. edge(const edge_coordinate& c) : coordinate(c) { }
  48. };
  49.  
  50. struct edge_map : public map<edge_coordinate, unique_ptr<edge> > {
  51. edge* obtain(const edge_coordinate& c) {
  52. auto i = lower_bound(c);
  53. if (i != end() && i->first == c)
  54. return i->second.get();
  55. unique_ptr<edge> e{new edge(c)};
  56. return insert(i, make_pair(c, std::move(e)))->second.get();
  57. }
  58. };
  59.  
  60. void printem(const point* a, const point* b, const point* c);
  61.  
  62. struct point {
  63. int x, y;
  64. edge *e1, *e2;
  65.  
  66. point(int xx, int yy) : x(xx), y(yy) { }
  67. void find_triangles() const {
  68. for (auto i: e1->pts2) {
  69. if (i < this) continue;
  70. for (auto j: e2->pts1) {
  71. if (j < this) continue;
  72. if (i->e1 == j->e2) {
  73. printem(this, i, j);
  74. }
  75. }
  76. }
  77. }
  78. };
  79.  
  80. void printem(const point* a, const point* b, const point* c) {
  81. printf("(%3d,%3d) (%3d,%3d) (%3d,%3d)\n", a->x, a->y, b->x, b->y, c->x, c->y);
  82. }
  83.  
  84. void findem(int m) {
  85. edge_map edges;
  86. vector< unique_ptr<point> > pts;
  87. for (int x = -m; x <= m; ++x) {
  88. for (int y = -m; y <= m; ++y) {
  89. int dd = x*x + y*y - 25;
  90. if (dd <= 0) continue;
  91. int d = int(sqrt(dd) + .5);
  92. if (d*d != dd) continue;
  93. pts.push_back(unique_ptr<point>(new point(x, y)));
  94. point* p = pts.back().get();
  95. edge_coordinate ec1(x, y, d), ec2(x, y, -d);
  96. edge *e1 = edges.obtain(ec1), *e2 = edges.obtain(ec2);
  97. p->e1 = e1;
  98. p->e2 = e2;
  99. e1->pts1.insert(p);
  100. e2->pts2.insert(p);
  101. }
  102. }
  103. for (auto& p: pts) {
  104. p->find_triangles();
  105. }
  106. }
  107.  
  108. int main(int argc, char** argv) {
  109. findem(100);
  110. }
  111.  
Success #stdin #stdout 0s 3564KB
stdin
Standard input is empty
stdout
(-85,-30) ( -1,  5) ( 35,  5)
(-85, 30) ( 35, -5) ( -1, -5)
(-75, -5) ( 37, 10) (  1, -5)
(-75,  5) (  1,  5) ( 37,-10)
(-65,-55) ( -2,  5) ( 15,  5)
(-65, 55) ( 15, -5) ( -2, -5)
(-55,-65) (  5, 15) (  5, -2)
(-55,-35) (  5, 10) (  5, -3)
(-55, -5) (  5,  6) (  5, -5)
(-55,  5) (  5,  5) (  5, -6)
(-55, 35) (  5,  3) (  5,-10)
(-55, 65) (  5,  2) (  5,-15)
(-50, -5) ( 49, 15) (  1, -5)
(-50,  5) (  1,  5) ( 49,-15)
(-49,-15) ( -1,  5) ( 50,  5)
(-49, 15) ( 50, -5) ( -1, -5)
(-37,-10) ( -1,  5) ( 75,  5)
(-37, 10) ( 75, -5) ( -1, -5)
(-35,-55) ( -3,  5) ( 10,  5)
(-35, -5) ( 85, 30) (  1, -5)
(-35,  5) (  1,  5) ( 85,-30)
(-35, 55) ( 10, -5) ( -3, -5)
(-30,-85) (  5, 35) (  5, -1)
(-30, -5) (  5,  7) (  5, -5)
(-30,  5) (  5,  5) (  5, -7)
(-30, 85) (  5,  1) (  5,-35)
(-25, -5) ( 11, 10) (  3, -5)
(-25, -5) ( 23, 15) (  2, -5)
(-25,  5) (  2,  5) ( 23,-15)
(-25,  5) (  3,  5) ( 11,-10)
(-23,-15) ( -2,  5) ( 25,  5)
(-23, 15) ( 25, -5) ( -2, -5)
(-15,-49) (  5, 50) (  5, -1)
(-15,-23) (  5, 25) (  5, -2)
(-15, -5) (  1,  7) ( 10, -5)
(-15, -5) (  5, 10) (  5, -5)
(-15, -5) ( 65, 55) (  2, -5)
(-15,  5) (  2,  5) ( 65,-55)
(-15,  5) (  5,  5) (  5,-10)
(-15,  5) ( 10,  5) (  1, -7)
(-15, 23) (  5,  2) (  5,-25)
(-15, 49) (  5,  1) (  5,-50)
(-13, -9) ( -1,  7) ( 11, -2)
(-13,  9) ( 11,  2) ( -1, -7)
(-11,-10) ( -3,  5) ( 25,  5)
(-11, -2) (  1,  7) ( 13, -9)
(-11,  2) ( 13,  9) (  1, -7)
(-11, 10) ( 25, -5) ( -3, -5)
(-10,-37) (  5, 75) (  5, -1)
(-10,-11) (  5, 25) (  5, -3)
(-10, -5) ( -1,  7) ( 15, -5)
(-10, -5) (  5, 15) (  5, -5)
(-10, -5) ( 35, 55) (  3, -5)
(-10,  5) (  3,  5) ( 35,-55)
(-10,  5) (  5,  5) (  5,-15)
(-10,  5) ( 15,  5) ( -1, -7)
(-10, 11) (  5,  3) (  5,-25)
(-10, 37) (  5,  1) (  5,-75)
( -9,-13) ( -2, 11) (  7, -1)
( -9, 13) (  7,  1) ( -2,-11)
( -7, -5) (  5, 30) (  5, -5)
( -7, -1) (  2, 11) (  9,-13)
( -7, -1) (  5, 15) (  5,-10)
( -7,  1) (  5, 10) (  5,-15)
( -7,  1) (  9, 13) (  2,-11)
( -7,  5) (  5,  5) (  5,-30)
( -6, -5) (  5, 55) (  5, -5)
( -6,  5) (  5,  5) (  5,-55)
( -5,-75) ( -5,  1) ( 10, 37)
( -5,-55) ( -5,  5) (  6,  5)
( -5,-50) ( -5,  1) ( 15, 49)
( -5,-35) ( -5,  1) ( 30, 85)
( -5,-30) ( -5,  5) (  7,  5)
( -5,-25) ( -5,  2) ( 15, 23)
( -5,-25) ( -5,  3) ( 10, 11)
( -5,-15) ( -5,  2) ( 55, 65)
( -5,-15) ( -5,  5) ( 10,  5)
( -5,-15) ( -5, 10) (  7,  1)
( -5,-10) ( -5,  3) ( 55, 35)
( -5,-10) ( -5,  5) ( 15,  5)
( -5,-10) ( -5, 15) (  7, -1)
( -5, -7) ( -5,  5) ( 30,  5)
( -5, -6) ( -5,  5) ( 55,  5)
( -5, -5) ( -5,  6) ( 55, -5)
( -5, -5) ( -5,  7) ( 30, -5)
( -5, -5) ( -5, 10) ( 15, -5)
( -5, -5) ( -5, 15) ( 10, -5)
( -5, -5) ( -5, 30) (  7, -5)
( -5, -5) ( -5, 55) (  6, -5)
( -5, -3) ( -5, 10) ( 55,-35)
( -5, -3) ( -5, 25) ( 10,-11)
( -5, -2) ( -5, 15) ( 55,-65)
( -5, -2) ( -5, 25) ( 15,-23)
( -5, -1) ( -5, 35) ( 30,-85)
( -5, -1) ( -5, 50) ( 15,-49)
( -5, -1) ( -5, 75) ( 10,-37)