#377298 (C++11) No.199 星を描こう

• 問題: No.199 星を描こう
• ユーザー: nonpro3_shojin
• 提出日時: 2019-09-07 19:31:52
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 2,317 bytes
• コンパイル時間: 866 ms
• コンパイル使用メモリ: 78,044 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-06-27 02:07:00
• 合計ジャッジ時間: 1,671 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	AC	2 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	AC	1 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	WA	-
testcase_15	AC	1 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	AC	1 ms; 5,376 KB
testcase_18	AC	2 ms; 5,376 KB
testcase_19	AC	1 ms; 5,376 KB
testcase_20	WA	-
testcase_21	AC	2 ms; 5,376 KB
testcase_22	WA	-
testcase_23	WA	-
testcase_24	AC	2 ms; 5,376 KB
testcase_25	AC	2 ms; 5,376 KB
testcase_26	WA	-
testcase_27	AC	1 ms; 5,376 KB

ソースコード

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