Submission #120325

#	Time	Username	Problem	Language	Result	Execution time	Memory
120325		tmwilliamlin168	Printed Circuit Board (CEOI12_circuit)	C++14	100 / 100	45 ms	4728 KiB

circuit

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

#define ll long long

const int mxN=2e5;
int n, l, r;
ll x[mxN+1], y[mxN+1];
vector<int> v, s;
bool b[mxN];

ll cp(int a, int b, int c) {
	return (y[c]-y[a])*(x[b]-x[a])-(y[b]-y[a])*(x[c]-x[a]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i=0; i<n; ++i) {
		cin >> x[i] >> y[i];
		if(!i||cp(n, l, i)>0||!cp(n, l, i)&&x[i]<x[l])
			l=i;
		if(!i||cp(n, r, i)<0||!cp(n, r, i)&&x[i]<x[r])
			r=i;
	}
	//cout << l << " " << r << endl;
	int ic=cp((l+n-1)%n, l, (l+1)%n)>0?1:n-1;
	for(; l^r; l=(l+ic)%n)
		v.push_back(l);
	v.push_back(r);
	//cout << "a" << endl;
	//for(int i : v)
		//cout << x[i] << " " << y[i] << endl;
	s={0, 1};
	for(int i=2; i<v.size(); ++i) {
		//cout << i << endl;
		//for(int si : s)
			//cout << si << " ";
		//cout << endl;
		//side going strictly forwards
		if(cp(n, v[i-1], v[i])<0) {
			//last side went strictly backwards and current side is now hidden
			if(cp(n, v[i-2], v[i-1])>0&&cp(v[i-2], v[i-1], v[i])<0) {
				//while hidden
				while(cp(n, v[s.back()], v[i])<=0)
					++i;
				s.pop_back();
				//while one of s.back() and i hides the other and it is actually s.back() which is hidden 
				while(cp(n, v[s.back()], v[i])>=0&&cp(v[i-1], v[i], v[s.back()])<0)
					s.pop_back();
				//i is hidden
				if(cp(n, v[s.back()], v[i])>=0) {
					int j=i, c=0;
					//while i is not to the right of s.back() or i is hidden by segment j
					while(cp(n, v[s.back()], v[i])>=0||!c) {
						//if this is the first side, c will be one iff the new edge goes forwards and is not hidden by segment j
						if(i==j)
							c=cp(n, v[i], v[i+1])<0&&cp(v[i-1], v[i], v[i+1])>0;
						//if we start not to the right of j but end up to the right of j and j does not hide i+1
						if(cp(n, v[j], v[i])>=0&&cp(n, v[j], v[i+1])<0&&cp(v[i], v[i+1], v[j])>0)
							++c;
						//if we start to the right of j but end up not to the right of j and j does not hide i+1
						if(cp(n, v[j], v[i])<0&&cp(n, v[j], v[i+1])>=0&&cp(v[i], v[i+1], v[j])<0)
							--c;
						++i;
					}
				}
			}
		}
		//side going strictly backwards
		else if(cp(n, v[i-1], v[i])>0) {
			//last side went strictly forwards and current side is now hidden
			if(cp(n, v[i-2], v[i-1])<0&&cp(v[i-2], v[i-1], v[i])>0) {
				//while hidden
				while(cp(n, v[s.back()], v[i])>=0)
					++i;
			} else {
				//while one of s.back() and i hides the other and it is actually s.back() which is hidden
				//note <= here so we can pop off v[i-1]
				while(cp(n, v[s.back()], v[i])>=0&&cp(v[i-1], v[i], v[s.back()])<=0)
					s.pop_back();
				//i is hidden
				if(cp(n, v[s.back()], v[i])>=0) {
					int j=i, c=0;
					//while i is not to the right of s.back() or i is hidden by segment j
					while(cp(n, v[s.back()], v[i])>=0||!c) {
						//if this is the first side, c will be one iff the new edge goes forwards and is not hidden by segment j
						if(i==j)
							c=cp(n, v[i], v[i+1])<0&&cp(v[i-1], v[i], v[i+1])>0;
						//if we start not to the right of j but end up to the right of j and j does not hide i+1
						if(cp(n, v[j], v[i])>=0&&cp(n, v[j], v[i+1])<0&&cp(v[i], v[i+1], v[j])>0)
							++c;
						//if we start to the right of j but end up not to the right of j and j does not hide i+1
						if(cp(n, v[j], v[i])<0&&cp(n, v[j], v[i+1])>=0&&cp(v[i], v[i+1], v[j])<0)
							--c;
						++i;
					}
				}
			}
		}
		//side not changing angle
		else {
			//if new point hides old point
			if((cp(n, v[i-2], v[i-1])<0)==(cp(v[i-2], v[i-1], v[i])<0))
				s.pop_back();
			//last side went strictly forwards and current side is now hidden
			else if(cp(n, v[i-2], v[i-1])<0) {
				//while hidden
				while(cp(n, v[s.back()], v[i])>=0)
					++i;
			}
			//last side went strictly backwards and current side is now hidden
			else {
				//while hidden
				while(cp(n, v[s.back()], v[i])<=0)
					++i;
				s.pop_back();
				//while one of s.back() and i hides the other and it is actually s.back() which is hidden 
				while(cp(n, v[s.back()], v[i])>=0&&cp(v[i-1], v[i], v[s.back()])<0)
					s.pop_back();
				//i is hidden
				if(cp(n, v[s.back()], v[i])>=0) {
					int j=i, c=0;
					//while i is not to the right of s.back() or i is hidden by segment j
					while(cp(n, v[s.back()], v[i])>=0||!c) {
						//if this is the first side, c will be one iff the new edge goes forwards and is not hidden by segment j
						if(i==j)
							c=cp(n, v[i], v[i+1])<0&&cp(v[i-1], v[i], v[i+1])>0;
						//if we start not to the right of j but end up to the right of j and j does not hide i+1
						if(cp(n, v[j], v[i])>=0&&cp(n, v[j], v[i+1])<0&&cp(v[i], v[i+1], v[j])>0)
							++c;
						//if we start to the right of j but end up not to the right of j and j does not hide i+1
						if(cp(n, v[j], v[i])<0&&cp(n, v[j], v[i+1])>=0&&cp(v[i], v[i+1], v[j])<0)
							--c;
						++i;
					}
				}
			}
		}
		s.push_back(i);
	}
	cout << s.size() << "\n";
	for(int a : s)
		b[v[a]]=1;
	for(int i=0; i<n; ++i)
		if(b[i])
			cout << i+1 << " ";
}

Compilation message (stderr)

circuit.cpp: In function 'int main()':
circuit.cpp:23:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(!i||cp(n, l, i)>0||!cp(n, l, i)&&x[i]<x[l])
                         ~~~~~~~~~~~~^~~~~~~~~~~
circuit.cpp:25:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(!i||cp(n, r, i)<0||!cp(n, r, i)&&x[i]<x[r])
                         ~~~~~~~~~~~~^~~~~~~~~~~
circuit.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=2; i<v.size(); ++i) {
               ~^~~~~~~~~

• Subtask 1: 100 / 100