結果
問題 |
No.455 冬の大三角
|
ユーザー |
![]() |
提出日時 | 2018-03-29 23:11:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,701 bytes |
コンパイル時間 | 864 ms |
コンパイル使用メモリ | 90,652 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-30 05:41:21 |
合計ジャッジ時間 | 2,956 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 54 |
ソースコード
// No.455 冬の大三角 // https://yukicoder.me/problems/no/455 // #include <iostream> #include <vector> #include <string> #include <cmath> #include <utility> #include <random> using namespace std; pair<int, int> solve(vector<pair<int, int>>& stars, int H, int W); struct Point { double x; double y; }; int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); int H, W; cin >> H >> W; vector<pair<int, int>> stars; string t; getline(cin, t); vector<string> field; for (int y = 0; y < H; ++y) { getline(cin, t); for (int x = 0; x < W; ++x) { if (t[x] == '*') stars.push_back(make_pair(x, y)); } field.push_back(t); } pair<int, int> ans = solve(stars, H, W); field[ans.second][ans.first] = '*'; for (int y = 0; y < H; ++y) cout << field[y] << endl; } pair<int, int> solve(vector<pair<int, int>>& stars, int H, int W) { random_device seed_gen; mt19937 engine(seed_gen()); uniform_int_distribution<> dist_x(0, W-1); uniform_int_distribution<> dist_y(0, H-1); while (true) { int x = dist_x(engine); int y = dist_y(engine); if (x == stars[0].first && y == stars[0].second) continue; if (x == stars[1].first && y == stars[1].second) continue; Point ab = {static_cast<double>(x) - stars[0].first, static_cast<double>(y) - stars[0].second}; Point ac = {static_cast<double>(x) - stars[1].first, static_cast<double>(y) - stars[1].second}; double cross = ab.x * ac.y - ab.y * ac.x; if (abs(cross) > 0.0001) return make_pair(x, y); } }