#include #include #include #include #include #include #include using std::string; struct Point { public: constexpr Point() noexcept : x(0), y(0) {} constexpr Point(int x, int y) noexcept : x(x), y(y) {} bool operator==(const Point& p) const { return x == p.x && y == p.y; } int x, y; }; struct Space { public: explicit Space(int h, int w, std::vector space) : h(h), w(w), space(space) {} void parse() noexcept { int x {0}; int y {0}; int found {0}; for (auto line : space) { for (auto e : line) { if (e == '*') { ((found == 0) ? p1 : p2) = Point(x, y); ++found; } ++x; } x = 0; ++y; } } Point lastStar() const { Point p3; std::random_device rnd; std::mt19937 mt(rnd()); std::uniform_real_distribution<> rand_x(0, w); std::uniform_real_distribution<> rand_y(0, h); for (;;) { p3 = Point(rand_x(mt), rand_y(mt)); if (isTriangle(p1, p2, p3)) { return p3; } } } void dot(const Point p) noexcept { int x {p.x}; int y {p.y}; space[y][x] = '*'; } void print() const noexcept { for (string line : space) { std::cout << line << '\n'; } } bool isHorizontal(const Point p1, const Point p2, const Point p3) const noexcept { return p1.y == p2.y && p1.y == p3.y; } bool isVertical(const Point p1, const Point p2, const Point p3) const noexcept { return p1.x == p2.x && p1.x == p3.x; } bool isSlanting(const Point p1, const Point p2, const Point p3) const noexcept { return (p2.y-p1.y) / double(p2.x-p1.x) == (p3.y-p1.y) / double(p3.x-p1.x); } bool isCoincidence(const Point p1, const Point p2, const Point p3) const noexcept { return p1 == p2 || p2 == p3 || p3 == p1; } bool isTriangle(const Point p1, const Point p2, const Point p3) const { if (isCoincidence(p1, p2, p3)) { return false; } if (isHorizontal(p1, p2, p3)) { return false; } if (isVertical(p1, p2, p3)) { return false; } if (isSlanting(p1, p2, p3)) { return false; } return true; } private: int h, w; std::vector space; Point p1; Point p2; }; int main() { int h, w; std::cin >> h >> w; std::vector space; for (int i = 0; i < h; ++i) { string s; std::cin >> s; space.push_back(s); } Space sp {h, w, space}; sp.parse(); Point p3 {sp.lastStar()}; sp.dot(p3); sp.print(); }