Submission #594844

#	Time	Username	Problem	Language	Result	Execution time	Memory
594844		penguinhacker	Triangles (CEOI18_tri)	C++17	0 / 100	3073 ms	344 KiB

tri

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

#define ll long long
#define ar array

// solution idea: find any point on the hull
// after this just use graham scan: sort by angle and then sweep

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n=get_n();
	/*int a=1, b=2, c=3;
	for (int i=4; i<=n; ++i) {
		bool s1=is_clockwise(a, b, i), s2=is_clockwise(b, c, i), s3=is_clockwise(c, a, i), s4=is_clockwise(a, b, c);
		for (int rep=0; rep<3; ++rep) {
			if (s1==s3&&s1!=s4) {
				a=i;
				break;
			}
			swap(s1, s2);
			swap(s2, s3);
			swap(a, b);
			swap(b, c);
		}
	}*/
	vector<int> part[2];
	for (int i=3; i<=n; ++i)
		part[is_clockwise(1, 2, i)].push_back(i);
	int fix;
	int a=1, b=2;
	while(part[0].size()&&part[1].size()) {
		if (part[0].size()<part[1].size()) {
			swap(part[0], part[1]);
			swap(a, b);
		}
		int extreme=part[1][0];
		for (int i=1; i<part[1].size(); ++i)
			if (is_clockwise(a, extreme, part[1][i]))
				extreme=part[1][i];
		part[0].clear();
		part[1].clear();
		b=extreme;
		for (int i=1; i<=n; ++i)
			if (i!=a&&i!=b)
				part[is_clockwise(a, b, i)].push_back(i);
	}
	fix=a;
	vector<int> points;
	for (int i=1; i<=n; ++i)
		if (i!=fix)
			points.push_back(i);
	sort(points.begin(), points.end(), [&](int i, int j) { return is_clockwise(fix, j, i); });
	vector<int> hull={fix};
	for (int i : points) {
		while(hull.size()>=2&&is_clockwise(hull.end()[-2], hull.back(), i))
			hull.pop_back();
		hull.push_back(i);
	}
	give_answer(hull.size());
	return 0;
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for (int i=1; i<part[1].size(); ++i)
      |                 ~^~~~~~~~~~~~~~~

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