Submission #70541

#	Time	Username	Problem	Language	Result	Execution time	Memory
70541		ics0503	Triangles (CEOI18_tri)	C++14	20 / 100	4 ms	628 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);
}
void get_CV(vector<int>&a, vector<int>&res, int tt) {
	t = tt;
	sort(a.begin(), a.end(), sort_angle);
	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[ni], LCV[i])) {
			pj = (pj + 1) % RCV.size();
		}
		if (pj == 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[ni], LCV[i])) {
			pj = (pj + RCV.size() - 1) % RCV.size();
		}
		if (pj == 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:17: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:27:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 1; i < LCV.size(); i++) {
              ~~^~~~~~~~~~~~
tri.cpp:24:13: warning: unused variable 'nj' [-Wunused-variable]
  int i, pj, nj;
             ^~
tri.cpp: In function 'int main()':
tri.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < LCV.size(); i++)LV[i] = 1;
              ~~^~~~~~~~~~~~
tri.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < RCV.size(); i++)RV[i] = 1;
              ~~^~~~~~~~~~~~
tri.cpp:59:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < LCV.size(); i++)ans += LV[i];
              ~~^~~~~~~~~~~~
tri.cpp:60:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < RCV.size(); i++)ans += RV[i];
              ~~^~~~~~~~~~~~
tri.cpp:46:22: warning: unused variable 'j' [-Wunused-variable]
  int n = get_n(), i, j;
                      ^

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