Submission #858128

#	Time	Username	Problem	Language	Result	Execution time	Memory
858128		serifefedartar	Geometrija (COCI21_geometrija)	C++17	0 / 110	0 ms	348 KiB

geometrija

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 18; 
const ll INF = 1e15;
const ll MAXN = 2100;

struct P {
	ll x, y;
	void read() {
		cin >> x >> y;
	}
	bool operator <(P b) {
		return make_pair(x, y) < make_pair(b.x, b.y);
	}
	P operator -(P other) {
		return P{x - other.x, y - other.y};
	}
	ll operator *(P other) {
		return x * other.y - y * other.x;
	}
	ll comp(P A, P B) {
		return (A - *this) * (B - *this);
	}
};

int main() {
	fast
	int n;
	cin >> n;

	if (n == 2) {
		cout << "1\n";
		return 0;
	}

	vector<P> points;
	for (int i = 0; i < n; i++) {
		P newP;
		newP.read();
		points.push_back(newP);
	}
	sort(points.begin(), points.end());

	vector<P> hull, hull_now;
	for (int rep = 0; rep < 2; rep++) {
		for (auto pnt : points) {
			while (hull_now.size() >= 2) {
				P A = hull_now.end()[-2];
				P B = hull_now.end()[-1];
				if (A.comp(B, pnt) <= 0)
					break;
				hull_now.pop_back();
			}
			hull_now.push_back(pnt);
		}
		hull_now.pop_back();

		for (auto u : hull_now)
			hull.push_back(u);
		hull_now.clear();
		reverse(points.begin(), points.end());
	}

	if (hull.size() + 1 == n)
		cout << 2 * hull.size() << "\n";
	else
		cout << hull.size() << "\n";
}

Compilation message (stderr)

geometrija.cpp: In function 'int main()':
geometrija.cpp:70:22: warning: comparison of integer expressions of different signedness: 'std::vector<P>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |  if (hull.size() + 1 == n)
      |      ~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60