結果

問題 No.199 星を描こう
ユーザー nonpro3_shojinnonpro3_shojin
提出日時 2019-09-07 19:38:42
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,326 bytes
コンパイル時間 1,114 ms
コンパイル使用メモリ 138,572 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-05-07 19:30:02
合計ジャッジ時間 1,866 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 1 ms
5,376 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 1 ms
5,376 KB
testcase_21 WA -
testcase_22 AC 1 ms
5,376 KB
testcase_23 AC 1 ms
5,376 KB
testcase_24 WA -
testcase_25 WA -
testcase_26 AC 1 ms
5,376 KB
testcase_27 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:30:10: warning: returning reference to local temporary object [-Wreturn-stack-address]
   30 |                 return co2d(*this) += b;
      |                        ^~~~~~~~~~~
main.cpp:38:10: warning: returning reference to local temporary object [-Wreturn-stack-address]
   38 |                 return co2d(*this) -= b;
      |                        ^~~~~~~~~~~
2 warnings generated.

ソースコード

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 {
	vector<int> ans;
	void calc(vector<co2d>& candidate) {

		const int Size = candidate.size();

		vector<pair<double, int>> sortlist;
		for (int i = 0; i < Size; i++) {
			if (candidate[i] == co2d(0, 0))sortlist.push_back(make_pair(0, i));
			else sortlist.push_back(make_pair(atan2(candidate[i].y, candidate[i].x), i));
		}
		sort(sortlist.begin(), sortlist.end());
		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;
			}
		}
		for (int i = 0; i < Size; i++) {
			if (sortlist[i].second == idx) {
				idx = i;
				break;
			}
		}
		ans.push_back(idx);
		ans.push_back((idx + 1) % Size);
		
		for (int i = idx + 2; i < Size + idx; i++) {
			
			while (ans.size() >= 2 && 
				co2d(candidate[ans.back()] - candidate[ans[ans.size() - 2]]).
				cross(co2d(candidate[sortlist[i % Size].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