Submission #70585

#	Time	Username	Problem	Language	Result	Execution time	Memory
70585		ics0503	Triangles (CEOI18_tri)	C++14	100 / 100	47 ms	2040 KiB

tri

#include<stdio.h>
#include"trilib.h"
#include<vector>
#include<algorithm>
using namespace std;
vector<int>L, R, LCV, RCV;
int ccw(int a, int b, int c) {
	return is_clockwise(a, b, c); }
int t;
bool sort_angle(int a, int b) {
	if (a == 1)return 1;
	if (b == 1)return 0;
	return t^ccw(1, a, b);
}
int temp[41414];
void sort_V(vector<int>&a, int s, int e) {
	if (s == e)return;
	int m = (s + e) / 2;
	sort_V(a, s, m);sort_V(a, m + 1, e);
	int p1 = s, p2 = m + 1;
	for (int i = s; i <= e; i++) {
		if (p1 == m + 1 || (p2 != e + 1 && !sort_angle(a[p1], a[p2]))) temp[i] = a[p2++];
		else temp[i] = a[p1++];
	}
	for (int i = s; i <= e; i++)a[i] = temp[i];
}
void get_CV(vector<int>&a, vector<int>&res, int tt) {
	t = tt;
	sort_V(a, 0, a.size() - 1);
	for (int i = 0; i < a.size(); i++) {
		while (res.size() >= 2 && (!t)^ccw(res[res.size() - 2], res[res.size() - 1], a[i]))res.pop_back();
		res.push_back(a[i]);
	}
}
int	LV[41414],RV[41414];
void VALIDCK(vector<int>&LCV, vector<int>&RCV, int LV[],int t) {
	int i, pj, nj;
	if (RCV.size() == 2)return;
	pj = 2;
	for (i = 1; i < LCV.size(); i++) {
		int ni = (i + 1) % LCV.size();
		while (pj != 0 && (!t)^ccw(RCV[pj], LCV[i], LCV[0]) && t^ccw(RCV[pj], LCV[ni], LCV[i])) {
			pj = (pj + 1) % RCV.size();
		}
		if (pj==0 || t^ccw(RCV[pj], LCV[i], LCV[0]))break;
		LV[i] = 0;
	}
	pj = RCV.size()-1;
	for (i = 0; i != 1; i = (i + LCV.size() - 1) % LCV.size()) {
		int ni = (i + LCV.size() - 1) % LCV.size();
		while (pj!=1 && t^ccw(RCV[pj],LCV[i],LCV[1]) && (!t)^ccw(RCV[pj], LCV[ni], LCV[i])) {
			pj = (pj + RCV.size() - 1) % RCV.size();
		}
		if (pj == 1 || (!t)^ccw(RCV[pj], LCV[i], LCV[1]))break;
		LV[i] = 0;
	}
}
int main() {
	int n = get_n(), i, j;
	L.push_back(1), L.push_back(2);
	R.push_back(1), R.push_back(2);
	for (i = 3; i <= n; i++) {
		if (ccw(1, 2, i))L.push_back(i);
		else R.push_back(i);
	}
	get_CV(L, LCV,0), get_CV(R, RCV, 1);
	for (i = 0; i < LCV.size(); i++)LV[i] = 1;
	for (i = 0; i < RCV.size(); i++)RV[i] = 1;
	VALIDCK(LCV, RCV, LV,1);
	VALIDCK(RCV, LCV, RV,0);
	int ans = 0;
	for (i = 0; i < LCV.size(); i++)ans += LV[i];
	for (i = 0; i < RCV.size(); i++)ans += RV[i];
	ans -= LV[0]; ans -= LV[1];
	give_answer(ans);
	return 0;
}

Compilation message (stderr)

tri.cpp: In function 'void get_CV(std::vector<int>&, std::vector<int>&, int)':
tri.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++) {
                  ~~^~~~~~~~~~
tri.cpp: In function 'void VALIDCK(std::vector<int>&, std::vector<int>&, int*, int)':
tri.cpp:40:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 1; i < LCV.size(); i++) {
              ~~^~~~~~~~~~~~
tri.cpp:37:13: warning: unused variable 'nj' [-Wunused-variable]
  int i, pj, nj;
             ^~
tri.cpp: In function 'int main()':
tri.cpp:67:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < LCV.size(); i++)LV[i] = 1;
              ~~^~~~~~~~~~~~
tri.cpp:68:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < RCV.size(); i++)RV[i] = 1;
              ~~^~~~~~~~~~~~
tri.cpp:72:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < LCV.size(); i++)ans += LV[i];
              ~~^~~~~~~~~~~~
tri.cpp:73:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < RCV.size(); i++)ans += RV[i];
              ~~^~~~~~~~~~~~
tri.cpp:59:22: warning: unused variable 'j' [-Wunused-variable]
  int n = get_n(), i, j;
                      ^

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