結果
問題 | No.199 星を描こう |
ユーザー |
![]() |
提出日時 | 2020-12-18 10:06:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,380 bytes |
コンパイル時間 | 1,944 ms |
コンパイル使用メモリ | 203,424 KB |
最終ジャッジ日時 | 2025-01-17 02:49:09 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> using namespace std; vector<pair<int, int>> convex_hull(vector<pair<int, int>> V) { auto cross = [](pair<int, int> a, pair<int, int> b, pair<int, int> c) { b.first -= a.first; c.first -= a.first; b.second -= a.second; c.second -= a.second; return (long long)b.first * c.second - (long long)b.second * c.first; }; int n = (int)V.size(); sort(V.begin(), V.end(), [](pair<int, int> a, pair<int, int> b) { return a.first != b.first ? a.first < b.first : a.second < b.second; }); if (n == 1) return V; int k = 0; vector<pair<int, int>> ret(n * 2); for (int i = 0; i < n; i++) { while (k > 1 && cross(ret[k - 1], V[i], ret[k - 2]) >= 0) k--; ret[k++] = V[i]; } for (int i = n - 2, t = k; i >= 0; i--) { while (k > t && cross(ret[k - 1], V[i], ret[k - 2]) >= 0) k--; ret[k++] = V[i]; } ret.resize(k - 1); return ret; } int main() { vector<pair<int, int>> P(5); for (int i = 0; i < 5; i++) { cin >> P[i].first >> P[i].second; } bool flag = false; vector<int> perm(5); iota(perm.begin(), perm.end(), 0); do { flag |= convex_hull(P).size() == 5; } while (next_permutation(perm.begin(), perm.end())); cout << (flag ? "YES" : "NO") << endl; }