結果

問題 No.455 冬の大三角
ユーザー sora410_tsora410_t
提出日時 2017-11-03 19:45:56
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,875 bytes
コンパイル時間 749 ms
コンパイル使用メモリ 77,816 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-12 15:24:21
合計ジャッジ時間 3,841 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 2 ms
4,384 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 2 ms
4,380 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 1 ms
4,380 KB
testcase_25 AC 1 ms
4,380 KB
testcase_26 AC 2 ms
4,380 KB
testcase_27 AC 2 ms
4,380 KB
testcase_28 AC 1 ms
4,376 KB
testcase_29 AC 2 ms
4,380 KB
testcase_30 AC 2 ms
4,376 KB
testcase_31 AC 2 ms
4,380 KB
testcase_32 AC 1 ms
4,380 KB
testcase_33 AC 2 ms
4,380 KB
testcase_34 AC 2 ms
4,384 KB
testcase_35 AC 2 ms
4,376 KB
testcase_36 AC 2 ms
4,380 KB
testcase_37 AC 1 ms
4,380 KB
testcase_38 AC 1 ms
4,380 KB
testcase_39 AC 2 ms
4,380 KB
testcase_40 AC 1 ms
4,380 KB
testcase_41 AC 2 ms
4,380 KB
testcase_42 AC 2 ms
4,380 KB
testcase_43 AC 2 ms
4,380 KB
testcase_44 AC 2 ms
4,380 KB
testcase_45 AC 2 ms
4,380 KB
testcase_46 AC 2 ms
4,380 KB
testcase_47 AC 2 ms
4,380 KB
testcase_48 AC 2 ms
4,380 KB
testcase_49 AC 2 ms
4,380 KB
testcase_50 AC 2 ms
4,376 KB
testcase_51 AC 1 ms
4,376 KB
testcase_52 AC 1 ms
4,384 KB
testcase_53 AC 2 ms
4,380 KB
testcase_54 AC 2 ms
4,384 KB
testcase_55 AC 2 ms
4,380 KB
testcase_56 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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