Submission #169848

#	Time	Username	Problem	Language	Result	Execution time	Memory
169848		arnold518	Triangles (CEOI18_tri)	C++14	20 / 100	3 ms	380 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 40000;

int N, p, q;
vector<int> A, B, D, C;

bool ccw(int a, int b, int c) { return !is_clockwise(a, b, c); }

int main()
{
	int i, j;
	N=get_n();

	for(i=3; i<=N; i++)
	{
		if(ccw(1, 2, i)) A.push_back(i);
		else B.push_back(i);
	}

	A.push_back(2); B.push_back(2);
	sort(A.begin(), A.end(), [&](const int &p, const int &q) { return ccw(1, p, q); });
	sort(B.begin(), B.end(), [&](const int &p, const int &q) { return !ccw(1, p, q); });

	A.insert(A.begin(), 1);
	B.insert(B.begin(), 1);

	vector<int> S;
	for(auto it : A)
	{
		while(S.size()>1 && !ccw(S[S.size()-2], S[S.size()-1], it)) S.pop_back();
		S.push_back(it);
	}
	A=S; S.clear();

	for(auto it : B)
	{
		while(S.size()>1 && ccw(S[S.size()-2], S[S.size()-1], it)) S.pop_back();
		S.push_back(it);
	}
	B=S; S.clear();	

	A.erase(A.begin()); A.erase(A.begin());
	B.erase(B.begin()); B.erase(B.begin()); 

	//for(auto it : A) printf("%d ", it); printf("\n");
	//for(auto it : B) printf("%d ", it); printf("\n");

	vector<int> T;
	T=A; reverse(T.begin(), T.end()); T.push_back(2);
	for(i=0; i<B.size(); i++) while(T.size()>1 && !ccw(B[i], T[T.size()-1], T[T.size()-2])) D.push_back(T.back()), T.pop_back();
	T.clear();

	T=B; reverse(T.begin(), T.end()); T.push_back(2);
	for(i=0; i<A.size(); i++) while(T.size()>1 && ccw(A[i], T[T.size()-1], T[T.size()-2])) D.push_back(T.back()), T.pop_back();
	T.clear();	

	T=A; T.push_back(1);
	for(i=B.size()-1; i>=0; i--) while(T.size()>1 && ccw(B[i], T[T.size()-1], T[T.size()-2])) D.push_back(T.back()), T.pop_back();
	T.clear();

	T=B; T.push_back(1);
	for(i=A.size()-1; i>=0; i--) while(T.size()>1 && !ccw(A[i], T[T.size()-1], T[T.size()-2])) D.push_back(T.back()), T.pop_back();
	T.clear();

	sort(D.begin(), D.end());
	D.erase(unique(D.begin(), D.end()), D.end());

	C.push_back(1); C.push_back(2);
	for(auto it : A) C.push_back(it);
	for(auto it : B) C.push_back(it);
	sort(C.begin(), C.end());
	C.erase(unique(C.begin(), C.end()), C.end());

	int ans=0;
	for(auto it : C) if(!binary_search(D.begin(), D.end(), it)) ans++;
	printf("%d", ans);
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:57:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<B.size(); i++) while(T.size()>1 && !ccw(B[i], T[T.size()-1], T[T.size()-2])) D.push_back(T.back()), T.pop_back();
           ~^~~~~~~~~
tri.cpp:61:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<A.size(); i++) while(T.size()>1 && ccw(A[i], T[T.size()-1], T[T.size()-2])) D.push_back(T.back()), T.pop_back();
           ~^~~~~~~~~
tri.cpp:18:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

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