Submission #74433

#	Time	Username	Problem	Language	Result	Execution time	Memory
74433		szawinis	Triangles (CEOI18_tri)	C++17	0 / 100	2 ms	576 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
#define long long long
using namespace std;

int n;
vector<int> up, down, up_hull, down_hull, ans;
int main() {
	n = get_n();
	for(int i = 3; i <= n; i++) {
		if(is_clockwise(1, 2, i)) down.push_back(i);
		else up.push_back(i);
	}
	up.push_back(2);
	down.push_back(2);
	sort(up.begin(), up.end(), [] (int j, int k) { return is_clockwise(1, j, k); });
	sort(down.begin(), down.end(), [] (int j, int k) { return !is_clockwise(1, j, k); });
	if(up.size() > 1) {
		up_hull.push_back(1);
		up_hull.push_back(up[0]);
		for(int i = 1; i < up.size(); i++) {
			while(up_hull.size() >= 2 && !is_clockwise(up_hull[up_hull.size()-2], up_hull[up_hull.size()-1], up[i]))
				up_hull.pop_back();
			up_hull.push_back(up[i]);
		}
	}
	if(down.size() > 1) {
		down_hull.push_back(1);
		down_hull.push_back(down[0]);
		for(int i = 1; i < down.size(); i++) {
			while(down_hull.size() >= 2 && is_clockwise(down_hull[down_hull.size()-2], down_hull[down_hull.size()-1], down[i]))
				down_hull.pop_back();
			down_hull.push_back(down[i]);
		}
	}

	if(!down_hull.empty() && !up_hull.empty()) {
		if(down_hull[0] == 1 && up_hull[0] == 1) down_hull.erase(down_hull.begin());
		if(down_hull.back() == 2 && up_hull.back() == 2) down_hull.pop_back();
	}
	reverse(down_hull.begin(), down_hull.end());
	vector<int> res = up_hull;
	for(int i: down_hull) res.push_back(i);
	
	ans.push_back(res[0]);
	ans.push_back(res[1]);
	for(int i = 2; i < res.size(); i++) {
		while(ans.size() >= 2 && !is_clockwise(ans[ans.size()-2], ans[ans.size()-1], res[i]))
			ans.pop_back();
		ans.push_back(res[i]);
	}

	/* for(int i: up) cout << i << ' '; */
	/* cout << endl; */
	/* for(int i: down) cout << i << ' '; */
	/* cout << endl; */
	/* for(int i: up_hull) cout << i << ' '; */
	/* cout << endl; */
	/* for(int i: down_hull) cout << i << ' '; */
	/* cout << endl; */
	/* for(int i: ans) cout << i << ' '; */
	/* cout << endl; */

	cout << ans.size() << endl;
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < up.size(); i++) {
                  ~~^~~~~~~~~~~
tri.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < down.size(); i++) {
                  ~~^~~~~~~~~~~~~
tri.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 2; i < res.size(); i++) {
                 ~~^~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 25