Submission #120376

#	Time	Username	Problem	Language	Result	Execution time	Memory
120376		tmwilliamlin168	Printed Circuit Board (CEOI12_circuit)	C++14	100 / 100	19 ms	4600 KiB

circuit

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

int in() {
	char c=0;
	while(c<'0'||c>'9')
		c=getchar_unlocked();
	int r=0;
	while(c>='0'&&c<='9') {
		r=r*10+c-'0';
		c=getchar_unlocked();
	}
	return r;
}

void out(int x) {
	int c=0, r=0;
	for(; x%10==0; ++c, x/=10);
	for(; x; r=r*10+x%10, x/=10);
	for(; r; r/=10)
		putchar_unlocked('0'+r%10);
	while(c--)
		putchar_unlocked('0');
}

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

int main() {
	auto cp=[](int a, int b, int c) {
		return (y[c]-y[a])*(x[b]-x[a])-(y[b]-y[a])*(x[c]-x[a]);
	};
	n=in();
	for(int i=0; i<n; ++i) {
		x[i]=in(), y[i]=in();
		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;
	}
	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);
	s={0, 1};
	for(int i=2; i<v.size(); ++i) {
		auto ul=[&]() {
			while(cp(n, v[s.back()], v[i])>=0&&cp(v[i-1], v[i], v[s.back()])<=0)
				s.pop_back();
			for(int j=i, c=cp(n, v[s.back()], v[i])<0; cp(n, v[s.back()], v[i])>=0||!c; ++i) {
				if(i^j?cp(n, v[j], v[i])>=0&&cp(n, v[j], v[i+1])<0&&cp(v[i], v[i+1], v[j])>0:cp(n, v[i], v[i+1])<0&&cp(v[i-1], v[i], v[i+1])>0)
					++c;
				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(!cp(n, v[i-1], v[i])&&(cp(n, v[i-2], v[i-1])<0)==(cp(v[i-2], v[i-1], v[i])<0))
			s.pop_back();
		else if(cp(n, v[i-1], v[i])<=0&&cp(n, v[i-2], v[i-1])>0&&cp(v[i-2], v[i-1], v[i])<0) {
			while(cp(n, v[s.back()], v[i])<=0)
				++i;
			s.pop_back();
			ul();
		} else if(cp(n, v[i-1], v[i])>0&&(cp(n, v[i-2], v[i-1])>=0||cp(v[i-2], v[i-1], v[i])<0))
			ul();
		else if(cp(n, v[i-1], v[i])>=0)
			while(cp(n, v[s.back()], v[i])>=0)
				++i;
		s.push_back(i);
	}
	out(s.size());
	putchar_unlocked('\n');
	for(int a : s)
		b[v[a]]=1;
	for(int i=0; i<n; ++i) {
		if(b[i]) {
			out(i+1);
			putchar_unlocked(' ');
		}
	}
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100