Submission #245937

#	Time	Username	Problem	Language	Result	Execution time	Memory
245937		eohomegrownapps	Triangles (CEOI18_tri)	C++14	0 / 100	5 ms	384 KiB

tri

#include "trilib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
int get_n();
int is_clockwise(int a, int b, int c);
void give_answer(int s);
*/

int n;

ll cns = 100000;
unordered_map<ll,bool> cwmap;

/*bool cwhash(int a, int b, int c){
	ll ct = a*cns*cns+b*cns+c;
	auto f = cwmap.find(ct);
	if (f!=cwmap.end()){
		return f->second;
	} else {
		return cwmap[ct]=bool(is_clockwise(a+1,b+1,c+1));
	}
}

bool cw(int a, int b, int c){
	//cout<<"cw "<<a<<" "<<b<<" "<<c<<" ";
	int minv = min(min(a,b),c);
	int tmp;
	if (a!=minv){
		tmp=a;a=b;b=c;c=tmp;
	}
	if (a!=minv){
		tmp=a;a=b;b=c;c=tmp;
	}
	bool ans;
	if (b<c){
		ans=cwhash(a,b,c);
	} else {
		ans=!cwhash(a,c,b);
	}
	//cout<<ans<<'\n';
	return ans;
}*/
bool cw(int a, int b, int c){
	return is_clockwise(a+1,b+1,c+1);
}

vector<int> convexhull(vector<int> &pts){
	/*cout<<"find hull ";
	for (int i : pts){
		cout<<i<<" ";
	}cout<<'\n';*/
	if (pts.size()<=3){
		return pts;
	}
	int a = pts[0];
	int b = pts[1];
	//a to b
	vector<int> lhs;
	vector<int> rhs;
	for (int i = 2; i<pts.size(); i++){
		if (cw(a,b,pts[i])){
			lhs.push_back(pts[i]);
		} else {
			rhs.push_back(pts[i]);
		}
	}
	if (lhs.size()>rhs.size()){
		swap(lhs,rhs);
		swap(a,b);
	}
	lhs.push_back(a);
	lhs.push_back(b);
	lhs = convexhull(lhs);
	rhs = convexhull(rhs);
	/*cout<<"merge:\n";
	for (int i : lhs){
		cout<<i<<" ";
	}cout<<'\n';
	for (int j : rhs){
		cout<<j<<" ";
	}cout<<'\n';*/
	//now in sorted order
	int leftpt = b;
	int rs = rhs.size();
	int ls = lhs.size();
	int rightpt = rhs[0];
	int leftind = -1;
	int rightind = 0;
	for (int i = 0; i<rs; i++){
		if (rhs.size()>1&&cw(rhs[(i+1)%rs],rhs[i],leftpt)){
			rightpt=rhs[i];
			rightind = i;
			break;
		}
	}
	assert(rightpt!=-1);
	leftind = find(lhs.begin(),lhs.end(),leftpt)-lhs.begin();
	//cout<<leftpt<<" "<<rightpt<<'\n';
	//cout<<leftind<<" "<<rightind<<'\n';
	int lp2 = leftind;
	int rp1 = rightind;
	bool check;
	bool condexit;
	do {
		check = true;
		condexit = true;
		while (lhs.size()>1&&!cw(rhs[rp1],lhs[lp2],lhs[(lp2+1)%ls])){
			if (lhs.size()>1&&rhs.size()>1&&!cw(lhs[(lp2+1)%ls],rhs[rp1],rhs[(rp1+rs-1)%rs])&&cw(rhs[rp1],rhs[(rp1+rs-1)%rs],lhs[lp2])){
				//check=false;
				condexit = false;
				break;
			}
			//cout<<"inc lp2\n";
			lp2+=1;
			lp2%=ls;
			check = false;
		}
		while (rhs.size()>1&&cw(lhs[lp2],rhs[rp1],rhs[(rp1+rs-1)%rs])){
			if (lhs.size()>1&&rhs.size()>1&&cw(rhs[(rp1+rs-1)%rs],lhs[lp2],lhs[(lp2+1)%ls])&&!cw(lhs[lp2],lhs[(lp2+1)%ls],rhs[rp1])){
				//check=false;
				condexit = false;
				break;
			}
			//cout<<"dec rp1\n";
			rp1+=rs-1;
			rp1%=rs;
			check = false;
		}
	} while (!check);
	assert(condexit==true);
	int lp1 = leftind;
	int rp2 = rightind;
	do {
		check = true;
		condexit = true;
		while (lhs.size()>1&&cw(rhs[rp2],lhs[lp1],lhs[(lp1+ls-1)%ls])){
			//cout<<"vis\n";
			//cout<<lhs[lp1]<<" "<<rhs[rp2]<<'\n';
			if (lhs.size()>1&&rhs.size()>1&&cw(lhs[(lp1+ls-1)%ls],rhs[rp2],rhs[(rp2+1)%rs])&&!cw(rhs[rp2],rhs[(rp2+1)%rs],lhs[lp1])){
				//check=false;
				condexit = false;
				break;
			}
			//cout<<"dec lp1\n";
			lp1+=ls-1;
			lp1%=ls;
			check = false;
		}
		while (rhs.size()>1&&!cw(lhs[lp1],rhs[rp2],rhs[(rp2+1)%rs])){
			if (lhs.size()>1&&rhs.size()>1&&!cw(rhs[(rp2+1)%rs],lhs[lp1],lhs[(lp1+ls-1)%ls])&&cw(lhs[lp1],lhs[(lp1+ls-1)%ls],rhs[rp2])){
				//check=false;
				condexit = false;
				break;
			}
			//cout<<"inc rp2\n";
			rp2+=1;
			rp2%=rs;
			check = false;
		}
	} while (!check);
	assert(condexit==true);
	//cout<<lhs[lp1]<<" "<<lhs[lp2]<<'\n';
	//cout<<rhs[rp1]<<" "<<rhs[rp2]<<'\n';
	vector<int> hull;
	int ptr;
	ptr = rp2;
	while (ptr!=rp1) {
		hull.push_back(rhs[ptr]);
		ptr++;
		ptr%=rs;
	}
	hull.push_back(rhs[ptr]);
	ptr = lp2;
	while (ptr!=lp1) {
		hull.push_back(lhs[ptr]);
		ptr++;
		ptr%=ls;
	}
	hull.push_back(lhs[ptr]);
	/*cout<<"hull contains ";
	for (int i : hull){
		cout<<i<<' ';
	}cout<<'\n';*/
	return hull;
}

int main(){
	n = get_n();
	vector<int> pts(n);
	iota(pts.begin(),pts.end(),0);
	give_answer(convexhull(pts).size());
}

Compilation message (stderr)

tri.cpp: In function 'std::vector<int> convexhull(std::vector<int>&)':
tri.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 2; i<pts.size(); i++){
                  ~^~~~~~~~~~~

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