結果

問題 No.199 星を描こう
ユーザー nonpro3_shojinnonpro3_shojin
提出日時 2019-09-07 19:35:26
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,326 bytes
コンパイル時間 762 ms
コンパイル使用メモリ 79,224 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-09 09:06:26
合計ジャッジ時間 2,059 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ（β）

テストケース

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

ソースコード

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