結果

問題 No.199 星を描こう
ユーザー nonpro3_shojinnonpro3_shojin
提出日時 2019-09-08 14:49:45
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,322 bytes
コンパイル時間 776 ms
コンパイル使用メモリ 77,712 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-27 14:59:05
合計ジャッジ時間 1,751 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 1 ms
6,944 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 WA -
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 1 ms
6,944 KB
testcase_17 AC 1 ms
6,944 KB
testcase_18 AC 1 ms
6,940 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 WA -
testcase_21 AC 2 ms
6,944 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 2 ms
6,940 KB
testcase_25 AC 2 ms
6,940 KB
testcase_26 WA -
testcase_27 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
In member function ‘bool co2d::operator==(const co2d&)’,
    inlined from ‘void convex_hull::calc(std::vector<co2d>&)’ at main.cpp:73:36:
main.cpp:17:32: warning: ‘<anonymous>.co2d::x’ may be used uninitialized [-Wmaybe-uninitialized]
   17 |                 return (*this).x == b.x && (*this).y == b.y;
      |                        ~~~~~~~~^
main.cpp: In function ‘void convex_hull::calc(std::vector<co2d>&)’:
main.cpp:38:34: note: ‘<anonymous>’ declared here
   38 |                 return co2d(*this) -= b;
      |                                  ^
In member function ‘bool co2d::operator==(const co2d&)’,
    inlined from ‘void convex_hull::calc(std::vector<co2d>&)’ at main.cpp:73:36:
main.cpp:17:52: warning: ‘<anonymous>.co2d::y’ may be used uninitialized [-Wmaybe-uninitialized]
   17 |                 return (*this).x == b.x && (*this).y == b.y;
      |                                            ~~~~~~~~^
main.cpp: In function ‘void convex_hull::calc(std::vector<co2d>&)’:
main.cpp:38:34: note: ‘<anonymous>’ declared here
   38 |                 return co2d(*this) -= b;
      |                                  ^

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

typedef long long ll;

struct co2d {
	//2次元座標のクラス
	ll x, y;
	co2d() { x = 0, y = 0; }
	co2d(ll a, ll b) { x = a, y = b; }

	bool operator== (const co2d& b) {
		return (*this).x == b.x && (*this).y == b.y;
	}

	co2d& operator=(const co2d& b) {
		(*this).x = b.x, (*this).y = b.y;
		return (*this);
	}

	co2d& operator+=(const co2d& b) {
		x += b.x, y += b.y;
		return (*this);
	}
	co2d& operator+(const co2d& b) const {
		return co2d(*this) += b;
	}

	co2d& operator-=(const co2d& b) {
		x -= b.x, y -= b.y;
		return (*this);
	}
	co2d& operator-(const co2d& b) const {
		return co2d(*this) -= b;
	}

	ll dot(const co2d& b) {
		//return value is scalar.
		return x * b.x + y * b.y;
	}

	ll cross(const co2d& b) {
		//From the veiw point of deifne, cross product is vector.
		//but int 2d, cross product is also schalar value.
		return x * b.y - y * b.x;
	}

};

namespace convex_hull {

	const double EPS = 1e-10;

	vector<int> ans;
	void calc(vector<co2d>& 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++) {
			if (candidate[i] - co2d(sx, sy) == co2d(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(0);
		ans.push_back(1);

		for (int i = 2; i < Size; i++) {

			while (ans.size() >= 2 &&
				co2d(candidate[ans.back()] - candidate[ans[ans.size() - 2]]).
				cross(co2d(candidate[sortlist[i].second] - candidate[ans.back()])) <= 0) {
				//不適格な点を取り除く
				ans.pop_back();
			}
			ans.push_back(sortlist[i % Size].second);
		}
	}
}

int main() {

	vector<co2d> pos(5);
	for (int i = 0; i < 5; i++)cin >> pos[i].x >> pos[i].y;

	convex_hull::calc(pos);

	if (convex_hull::ans.size() == 5) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}

	return 0;
}
0