Submission #108435

#	Time	Username	Problem	Language	Result	Execution time	Memory
108435		tjd229	Triangles (CEOI18_tri)	C++14	100 / 100	34 ms	2752 KiB

tri

#include <stdio.h>
#include "trilib.h"
#include <vector>
#include <algorithm>
#include <queue>
#define pii pair<int,int>
using namespace std;
int piv = 1;
bool cmp(int a, int b) {
	return is_clockwise(piv,b,a);
}
void make_hull(vector<int> &h,vector<int> &v) {
	int i;
	for (i = 0; i < 2 && i < v.size(); ++i) h.push_back(v[i]);
	for (; i < v.size(); ++i) {
		while (h.size() > 1 && is_clockwise(h[h.size() - 2], h.back(), v[i]))
			h.pop_back();
		h.push_back(v[i]);
	}
}
int main() {
	int n = get_n();//[1,n]
	vector<int > u, d;
	vector<int> hu, hd,ans;
	for (int i = 3; i <= n; ++i) {
		if (is_clockwise(1, 2, i)) d.push_back(i);
		else u.push_back(i);
	}
	stable_sort(u.begin(), u.end(), cmp);
	stable_sort(d.begin(), d.end(), cmp);
	make_hull(hu, u); make_hull(hd, d);
	//for (auto p : hu) printf("u:%d\n", p);
	//for (auto p : hd) printf("d:%d\n", p);

	hu.push_back(1);
	for (auto p : hd) hu.push_back(p);
	hu.push_back(2);
	make_hull(ans,hu);
	//for (auto p : ans) printf("a1:%d\n", p);

	bool flag = 1;
	int pad = 0;
	while (flag) {
		flag = 0;					
		while (ans.size() - pad > 2 && is_clockwise(ans[ans.size() - 2], ans.back(), ans[pad]))
			ans.pop_back(),flag=1;	
		while (ans.size() - pad > 2 && is_clockwise(ans.back(), ans[pad], ans[pad+1]))
			++pad, flag = 1;
	}
	give_answer(ans.size()-pad);
	//for(int i=pad;i<ans.size();++i) printf("a2:%d\n", ans[i]);
	return 0;
}

Compilation message (stderr)

tri.cpp: In function 'void make_hull(std::vector<int>&, std::vector<int>&)':
tri.cpp:14:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < 2 && i < v.size(); ++i) h.push_back(v[i]);
                       ~~^~~~~~~~~~
tri.cpp:15:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (; i < v.size(); ++i) {
         ~~^~~~~~~~~~

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