結果
問題 | No.199 星を描こう |
ユーザー | nonpro3_shojin |
提出日時 | 2019-09-08 18:28:47 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 3,602 bytes |
コンパイル時間 | 986 ms |
コンパイル使用メモリ | 77,440 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-27 15:07:01 |
合計ジャッジ時間 | 1,673 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 1 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 1 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 1 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 1 ms
5,376 KB |
testcase_20 | AC | 1 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 1 ms
5,376 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 1 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 2 ms
5,376 KB |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; namespace v2d { struct Vec2 { //2次元ベクトルのクラス double x, y; Vec2(double _x, double _y) { x = _x, y = _y; } Vec2() { x = 0, y = 0; } Vec2 operator+() const { return *this; } Vec2 operator-() const { return{ -x, -y }; } Vec2 operator+ (const Vec2& b) const { return{ x + b.x, y + b.y }; } Vec2 operator- (const Vec2& b) const { return{ x - b.x, y - b.y }; } Vec2 operator* (const double b) const { return{ x * b, y * b }; } Vec2 operator/ (const double b) const { return{ x / b, y / b }; } Vec2 operator+= (const Vec2& b) { x += b.x, y += b.y; return *this; } Vec2 operator-= (const Vec2& b) { x -= b.x, y -= b.y; return *this; } Vec2 operator*= (const double b) { x *= b, y *= b; return *this; } Vec2 operator/= (const double b) { x /= b, y /= b; return *this; } bool operator== (const Vec2& b) { return b.x == x && b.y == y; } double lengthSquare() { return (x * x + y * y); } double length() { return std::sqrt(lengthSquare()); } double dot(const Vec2& b) { return x * b.x + y * b.y; } double cross(const Vec2& b) { //Generally, cross product is vector, but in 2D, cross product is also scalar. return x * b.y - y * b.x; } double distanceFrom(const Vec2& b) { return std::sqrt((x - b.x) * (x - b.x) + (y - b.y) * (y - b.y)); } Vec2 normalized() { return{ x / length(), y / length() }; } bool isZero() { return x == 0.0 && y == 0.0; } }; inline Vec2 operator*(double a, const Vec2& b) { return{ b.x * a, b.y * a }; } template <class Char> inline std::basic_ostream<Char>& operator <<(std::basic_ostream<Char>& os, const Vec2& v) { return os << Char('(') << v.x << Char(',') << v.y << Char(')'); } template <class Char> inline std::basic_istream<Char>& operator >> (std::basic_istream<Char>& is, Vec2& v) { return is >> v.x >> v.y; } } using namespace v2d; namespace convex_hull { const double EPS = 1e-10; vector<int> ans; void calc(vector<v2d::Vec2>& candidate) { const int Size = candidate.size(); ll sx = candidate[0].x, sy = candidate[0].y; int idx = 0; for (int i = 1; i < Size; i++) { if (sx >= candidate[i].x && sy >= candidate[i].y) { sx = candidate[i].x, sy = candidate[i].y, idx = i; } } vector<pair<double, int>> sortlist; for (int i = 0; i < Size; i++) { v2d::Vec2 tmp; if (v2d::Vec2(candidate[i].x - sx, candidate[i].y - sy) == v2d::Vec2(0, 0)) { sortlist.push_back(make_pair(-acos(-1) - 1.0, i));//始点が確実に最初に来るようにする } else { sortlist.push_back(make_pair(atan2(candidate[i].y - sy, candidate[i].x - sx), i)); } } sort(sortlist.begin(), sortlist.end()); ans.push_back(sortlist[0].second); ans.push_back(sortlist[1].second); for (int i = 2; i <= Size + 1; i++) { while (ans.size() >= 2 && v2d::Vec2(candidate[ans.back()] - candidate[ans[ans.size() - 2]]). cross(v2d::Vec2(candidate[sortlist[i % Size].second] - candidate[ans.back()])) <= 0) { //不適格な点を取り除く ans.pop_back(); } ans.push_back(sortlist[i % Size].second); } ans.pop_back();//最後で入れた2つの始点を除く ans.pop_back(); } } int main() { vector<Vec2> pos(5); for (int i = 0; i < 5; i++)cin >> pos[i]; convex_hull::calc(pos); if (convex_hull::ans.size() == 5) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0; }