結果

問題 No.455 冬の大三角
コンテスト
ユーザー sora410_t
提出日時 2017-11-03 19:45:56
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,875 bytes
コンパイル時間 700 ms
コンパイル使用メモリ 80,024 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-30 03:21:38
合計ジャッジ時間 2,671 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 54
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <cmath>
#include <random>
#include <ratio>

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<string> 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<string> space;
    Point p1;
    Point p2;
};

int main() {
    int h, w;
    std::cin >> h >> w;
    std::vector<string> 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();
}
0