QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#550#343612#7730. Convex Checker5ab5abFailed.2024-03-02 20:58:142024-03-02 20:58:14

Details

Extra Test:

Accepted
time: 1ms
memory: 3604kb

input:

7
3 2
3 5
5 3
4 3
4 3
1 4
5 5

output:

No

result:

ok answer is NO

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#343612#7730. Convex Checker5abAC ✓33ms7300kbC++202.0kb2024-03-02 20:13:132024-07-04 19:27:58

answer

/* name: 7730
 * author: 5ab
 * created at: 2024-03-02
 */
#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define ssz(x) (int((x).size()))

auto chmax = [](auto& x, auto y) { if (x < y) x = y; };
auto chmin = [](auto& x, auto y) { if (y < x) x = y; };

using ll = long long;
const int N = 2e5;

struct point
{
	int x, y;
	point operator-(const point& q) const {
		return { x - q.x, y - q.y };
	}
	bool operator==(const point& q) const {
		return x == q.x && y == q.y;
	}
}
a[N], b[N];

inline ll cross(const point& p, const point& q) {
	return 1ll * p.x * q.y - 1ll * q.x * p.y;
}
inline ll dot(const point& p, const point& q) {
	return 1ll * p.x * q.x + 1ll * p.y * q.y;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i].x >> a[i].y;
	copy(a, a + n, b);
	
	swap(b[0], *min_element(b, b + n, [](auto& p, auto& q) {
		return p.x == q.x ? p.y < q.y : p.x < q.x;
	}));
	sort(b + 1, b + n, [&](auto& p, auto& q) {
		ll t = cross(p - b[0], q - b[0]);
		return t ? t > 0 : dot(q - p, p - b[0]) > 0;
	});
	
	int lm = unique(b, b + n) - b;
	vector<point> cv;
	for (int i = 0; i < lm; i++)
	{
		while (ssz(cv) > 1 && cross(b[i] - cv.back(), cv.back() - end(cv)[-2]) >= 0)
			cv.pop_back();
		// cerr << b[i].x << " " << b[i].y << endl;
		cv.push_back(b[i]);
	}
	
	// cerr << ssz(cv) << " " << lm << endl;
	
	if (ssz(cv) != n)
	{
		cout << "No\n";
		return 0;
	}
	auto check = [&]() -> bool
	{
		int sp = find(a, a + n, cv[0]) - a;
		// cerr << sp << endl;
		if (sp == n)
			return 0;
		for (int i = 0, j = sp; i < n; i++, j = (j + 1) % n)
			if (a[j] != cv[i])
			{
				// cerr << i << " " << j << " " << cv[i].x << " " << cv[i].y << endl;
				return 0;
			}
		return 1;
	};
	
	bool res = check();
	reverse(all(cv));
	
	cout << ((check() || res) ? "Yes" : "No") << "\n";
	
	return 0;
}
// started coding at: 03-02 19:14:06