제출 #145910

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
145910		nvmdava	Triangles (CEOI18_tri)	C++17	0 / 100	2 ms	504 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;

map<ll, bool> lol;

bool get(ll a, ll b, ll c){
	ll en = a * 40001 * 40001 + b * 40001 + c;
	if(lol.find(en) != lol.end())
		return lol[en];
	return lol[en] = is_clockwise(a, b, c);
}

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 = 3; i < hull.size(); i++){
 		while(hull2.size() > 2 && get(hull2[hull2.size() - 2], hull2[hull2.size() - 1], hull[i])) hull2.pop_back();
 		hull2.push_back(hull[i]);
 	}

 	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());
}

컴파일 시 표준 에러 (stderr) 메시지

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

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