Submission #145914

# Submission time Handle Problem Language Result Execution time Memory
145914 2019-08-21T11:04:30 Z nvmdava Triangles (CEOI18_tri) C++17
Compilation error
0 ms 0 KB
#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;

map<ll, bool> lol;

ll enc(ll a, ll b, ll c){
	return a * 40001 * 40001 + b * 40001 + c
}

bool get(ll a, ll b, ll c){
	ll en = enc(a, b, c);
	if(lol.find(en) != lol.end())
		return lol[en];
	int res = is_clockwise(a, b, c);
	lol[enc(a, b, c)] = lol[enc(b, c, a)] = lol[enc(c, a, b)] = res;
	lol[enc(c, b, a)] = lol[enc(b, a, c)] = lol[enc(a, c, b)] = res ^ 1;
	return res;
}

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


set<int, Compare> le, ri;
vector<int> hull, hull2;
int main() {
 
	n = get_n();
 
 	root = rng() % n + 1;
 	t = rng() % n + 1;
 	while(root == t){
 		root = rng() % n + 1;
 		t = rng() % n + 1;
 	}
 	
 	for(int i = 1; i <= n; i++){
 		if(root == i || t == i) continue;
 		if(get(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);

 	int v1 = hull[0];
 	int v2 = hull[1];
 	hull2.push_back(v1);
 	hull2.push_back(v2);
 	for(int i = 2; i < hull.size(); i++){
 		while(hull2.size() > 2 && get(hull2[hull2.size() - 2], hull2[hull2.size() - 1], hull[i]) == 0) hull2.pop_back();
 		hull2.push_back(hull[i]);
 	}

 	swap(hull2, hull);
 	hull2.clear();

 	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(!hull2.empty())
 				l = hull2.back();

 			if(get(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

tri.cpp: In function 'long long int enc(long long int, long long int, long long int)':
tri.cpp:16:1: error: expected ';' before '}' token
 }
 ^
tri.cpp: In function 'int main()':
tri.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 2; i < hull.size(); i++){
                  ~~^~~~~~~~~~~~~
tri.cpp:77:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < hull.size(); i++){
                   ~~^~~~~~~~~~~~~
tri.cpp:81:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(r == hull.size()) r = 0;
        ~~^~~~~~~~~~~~~~