結果

問題 No.199 星を描こう
ユーザー nonpro3_shojinnonpro3_shojin
提出日時 2019-09-08 18:19:02
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,573 bytes
コンパイル時間 944 ms
コンパイル使用メモリ 77,284 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-27 15:06:54
合計ジャッジ時間 1,867 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 WA -
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 2 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 2 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 WA -
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 1 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 1 ms
5,376 KB
testcase_21 AC 1 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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; 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();//最後で入れた始点を除く
	}
}

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;
}
0