Submission #145885

#	Time	Username	Problem	Language	Result	Execution time	Memory
145885		nvmdava	Triangles (CEOI18_tri)	C++17	75 / 100	46 ms	4232 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
 
#define ff first
#define ss second
#define ll long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int n, root, t;

class Compare{
	public:
		bool operator()(const int& lhs, const int& rhs){
			return is_clockwise(root, lhs, rhs);
		}
};

set<int, Compare> le, ri;
vector<int> hull, hull2;
int main() {
 
	n = get_n();
 
 	root = 1;
 	t = 2;
 	for(int i = 3; i <= n; i++){
 		if(is_clockwise(t, root, i))
 		 	ri.insert(i);
 		else 
 			le.insert(i);
 	}
 	for(int x : le)
 		hull.push_back(x);
 	hull.push_back(root);
 	for(int x : ri)
 		hull.push_back(x);
 	hull.push_back(t);
 	while(true){
 		for(int i = 0; i < hull.size(); i++){
 			int l = i - 1;
 			int r = i + 1;
 			if(l == -1) l = hull.size() - 1;
 			if(r == hull.size()) r = 0;
 			l = hull[l];
 			r = hull[r];

 			if(is_clockwise(l, hull[i], r))
 				hull2.push_back(hull[i]);
 		}
 		swap(hull2, hull);
 		if(hull.size() == hull2.size()) break;
 		hull2.clear();
 	}
 	give_answer(hull.size());
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:40:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < hull.size(); i++){
                   ~~^~~~~~~~~~~~~
tri.cpp:44:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(r == hull.size()) r = 0;
        ~~^~~~~~~~~~~~~~

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