Submission #13592484


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct P {
	ll x, y;
	P() {}
	P(ll x_, ll y_) : x(x_), y(y_) {}
	friend istream& operator >> (istream& i, P& p) { return i >> p.x >> p.y; }
	friend ostream& operator << (ostream& o, P p) { return o << "(" << p.x << ", " << p.y << ")"; }
	friend bool operator < (P a, P b) { return make_pair(a.x, a.y) < make_pair(b.x, b.y); }
	friend P operator + (P a, P b) { return P(a.x + b.x, a.y + b.y); }
	friend P operator - (P a, P b) { return P(a.x - b.x, a.y - b.y); }
	friend ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
};

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n;
	cin >> n;
	vector<pair<P, int> > rocks(n);
	for (int i = 0; i < n; i++) {
		cin >> rocks[i].first;
		rocks[i].second = i;
	}
	sort(rocks.begin(), rocks.end());
	vector<pair<P, int> > polyline;
	polyline.reserve(n);
	for (int i = 0; i < n; i++) {
		pair<P, int> p = rocks[i];
		while (polyline.size() >= 2 && 
			   cross(polyline.end()[-1].first - polyline.end()[-2].first, 
					 p.first - polyline.end()[-1].first) < 0) {
			polyline.pop_back();
		}
		polyline.push_back(p);
	}
	if (int(polyline.size()) == n) {
		bool bad = true;
		for (int i = 0; i+2 < n; i++) {
			bad &= cross(polyline[i+1].first - polyline[i].first, polyline[i+2].first - polyline[i+1].first) == 0;
		}
		if (bad) {
			cout << 0 << '\n';
			exit(0);
		}
	}
	vector<bool> done(n, false);
	for (int i = 0; i < int(polyline.size()); i++) {
		int idx = polyline[i].second;
		done[idx] = true;
		cout << idx+1 << '\n';
	}
	for (int i = n-1; i >= 0; i--) {
		if (!done[i]) {
			cout << i+1 << '\n';
		}
	}
}

Submission Info

Submission Time
Task B - Jumps
User iefnah06
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1693 Byte
Status IE