#include <map> #include <set> #include <vector> #include <memory> #include <cmath> #include <cstdio> using namespace std; struct point; int gcd(int a, int b) { if (a < 0) a = -a; if (b < 0) b = -b; if (a < b) swap(a, b); while (b != 0) { int c = a % b; a = b; b = c; } return a; } struct edge_coordinate { int a, b; edge_coordinate(int x, int y, int d) { int aa = 5*x + d*y; int bb = 5*y - d*x; int g = gcd(aa, bb); a = aa/g; b = bb/g; } bool operator<(const edge_coordinate& other) const { return (a != other.a) ? (a < other.a) : (b < other.b); } bool operator==(const edge_coordinate& other) const { return (a == other.a) && (b == other.b); } }; struct edge { edge_coordinate coordinate; set<point*> pts1; set<point*> pts2; edge(const edge_coordinate& c) : coordinate(c) { } }; struct edge_map : public map<edge_coordinate, unique_ptr<edge> > { edge* obtain(const edge_coordinate& c) { auto i = lower_bound(c); if (i != end() && i->first == c) return i->second.get(); unique_ptr<edge> e{new edge(c)}; return insert(i, make_pair(c, std::move(e)))->second.get(); } }; void printem(const point* a, const point* b, const point* c); struct point { int x, y; edge *e1, *e2; point(int xx, int yy) : x(xx), y(yy) { } void find_triangles() const { for (auto i: e1->pts2) { if (i < this) continue; for (auto j: e2->pts1) { if (j < this) continue; if (i->e1 == j->e2) { printem(this, i, j); } } } } }; pair<double, double> touching_point(const point* p) { double px = p->x, py = p->y, d = sqrt(px*px + py*py - 25); double x = 5*px + d*py, y = 5*py - d*px, f = 5/(px*px + py*py); return make_pair(x*f, y*f); } void printem(const point* a, const point* b, const point* c) { int ax = a->x, ay = a->y, bx = b->x, by = b->y, cx = c->x, cy = c->y; int abx = ax - bx, aby = ay - by, bcx = bx - cx, bcy = by - cy; int cax = cx - ax, cay = cy - ay; /* if (ax == -5 || ax == 5 || ay == -5 || ay == 5 || bx == -5 || bx == 5 || by == -5 || by == 5 || cx == -5 || cx == 5 || cy == -5 || cy == 5) return; // boring horizontal or vertical */ if ((abx*bcx + aby*bcy)*(bcx*cax + bcy*cay)*(cax*abx + cay*aby) == 0) return; // right-angled printf("(%3d,%3d) (%3d,%3d) (%3d,%3d)\n", a->x, a->y, b->x, b->y, c->x, c->y); } void findem(int m) { edge_map edges; vector< unique_ptr<point> > pts; for (int x = -m; x <= m; ++x) { for (int y = -m; y <= m; ++y) { int dd = x*x + y*y - 25; if (dd <= 0) continue; int d = int(round(sqrt(dd))); if (d*d != dd) continue; pts.push_back(unique_ptr<point>(new point(x, y))); point* p = pts.back().get(); edge_coordinate ec1(x, y, d), ec2(x, y, -d); edge *e1 = edges.obtain(ec1), *e2 = edges.obtain(ec2); p->e1 = e1; p->e2 = e2; e1->pts1.insert(p); e2->pts2.insert(p); } } for (auto& p: pts) { p->find_triangles(); } } int main(int argc, char** argv) { findem(300); }
Standard input is empty
(-275,-255) ( -2, 5) ( 13, 5) (-275,255) ( 13, -5) ( -2, -5) (-255,-275) ( 5, 13) ( 5, -2) (-255,275) ( 5, 2) ( 5,-13) (-145,-55) ( -1, 5) ( 30, 5) (-145, 55) ( 30, -5) ( -1, -5) (-130,-75) ( 5, 9) ( 5, -3) (-130, 75) ( 5, 3) ( 5, -9) (-85,-30) ( -1, 5) ( 35, 5) (-85, 30) ( 35, -5) ( -1, -5) (-75,-130) ( -3, 5) ( 9, 5) (-75, -5) ( 37, 10) ( 1, -5) (-75, 5) ( 1, 5) ( 37,-10) (-75,130) ( 9, -5) ( -3, -5) (-65,-55) ( -2, 5) ( 15, 5) (-65, 55) ( 15, -5) ( -2, -5) (-55,-145) ( 5, 30) ( 5, -1) (-55,-65) ( 5, 15) ( 5, -2) (-55,-35) ( 5, 10) ( 5, -3) (-55, 35) ( 5, 3) ( 5,-10) (-55, 65) ( 5, 2) ( 5,-15) (-55,145) ( 5, 1) ( 5,-30) (-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) (145, 55) ( 1, -5) (-30, 5) ( 1, 5) (145,-55) (-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) ( 65, 55) ( 2, -5) (-15, 5) ( 2, 5) ( 65,-55) (-15, 23) ( 5, 2) ( 5,-25) (-15, 49) ( 5, 1) ( 5,-50) (-13, -5) (275,255) ( 2, -5) (-13, 5) ( 2, 5) (275,-255) (-11,-10) ( -3, 5) ( 25, 5) (-11, 10) ( 25, -5) ( -3, -5) (-10,-37) ( 5, 75) ( 5, -1) (-10,-11) ( 5, 25) ( 5, -3) (-10, -5) ( 35, 55) ( 3, -5) (-10, 5) ( 3, 5) ( 35,-55) (-10, 11) ( 5, 3) ( 5,-25) (-10, 37) ( 5, 1) ( 5,-75) ( -9, -5) ( 75,130) ( 3, -5) ( -9, 5) ( 3, 5) ( 75,-130) ( -5,-75) ( -5, 1) ( 10, 37) ( -5,-50) ( -5, 1) ( 15, 49) ( -5,-35) ( -5, 1) ( 30, 85) ( -5,-30) ( -5, 1) ( 55,145) ( -5,-25) ( -5, 2) ( 15, 23) ( -5,-25) ( -5, 3) ( 10, 11) ( -5,-15) ( -5, 2) ( 55, 65) ( -5,-13) ( -5, 2) (255,275) ( -5,-10) ( -5, 3) ( 55, 35) ( -5, -9) ( -5, 3) (130, 75) ( -5, -3) ( -5, 9) (130,-75) ( -5, -3) ( -5, 10) ( 55,-35) ( -5, -3) ( -5, 25) ( 10,-11) ( -5, -2) ( -5, 13) (255,-275) ( -5, -2) ( -5, 15) ( 55,-65) ( -5, -2) ( -5, 25) ( 15,-23) ( -5, -1) ( -5, 30) ( 55,-145) ( -5, -1) ( -5, 35) ( 30,-85) ( -5, -1) ( -5, 50) ( 15,-49) ( -5, -1) ( -5, 75) ( 10,-37)