Submission #677492

#	Time	Username	Problem	Language	Result	Execution time	Memory
677492		vjudge1	Printed Circuit Board (CEOI12_circuit)	C++17	5 / 100	91 ms	29032 KiB

circuit

#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;

int n;
int X[maxn];
int Y[maxn];
map<ii, int> M;
vector<int> ans;
int sol[maxn];
ii P[maxn];

ll cross(ii p1, ii p2, ii p3) {return (ll)p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);}

ll dist(ii p1) {
	return (ll)p1.x * p1.x + p1.y * p1.y;
}

struct line {
	ii pL, pR;
	friend bool operator<(line l1, line l2) {
		if(dist(l1.pR) == dist(l2.pR)) 
			return dist(l1.pL) < dist(l2.pL);
		return dist(l1.pR) < dist(l2.pR);
	}
};

struct event {
	line l;
	ii p;
	int open;
	friend bool operator<(event a, event b) {
		if(a.p == b.p) return a.open > b.open;
		if(cross({0, 0}, a.p, b.p) == 0) return a.p.x > b.p.x;
		return cross({0, 0}, a.p, b.p) < 0;
	}
};

int main() {
	scanf("%d", &n);
	for(int i = 0;i < n;i++) 
		scanf("%d%d", X + i, Y + i), M[{X[i], Y[i]}] = i, P[i] = {X[i], Y[i]};
	X[n] = X[0];
	Y[n] = Y[0];
	
	vector<event> sweep;
	for(int i = 0;i < n;i++) {
		line l;
		l.pL = {X[i], Y[i]};
		l.pR = {X[i + 1], Y[i + 1]};
		if(cross({0, 0}, l.pL, l.pR) > 0) swap(l.pL, l.pR);
		event e;
		e.l = l, e.p = l.pL, e.open = 1;
		sweep.pb(e);
		e.p = l.pR, e.open = 0;
		sweep.pb(e);
	}
	 
	sort(all(sweep));
	set<line> s;
	line l1, l2;
	l1.pL = P[3], l1.pR = P[4];
	l2.pL = P[1], l2.pR = P[2];
	
	for(auto e : sweep) {
		if(e.open == 1) {
			if(s.size() == 0) sol[M[e.p]] = 1;
			else {
				line l = *s.begin();
				if(e.l < l) sol[M[e.p]] = 1;
			}
			s.insert(e.l);
		} else {
			if(s.size() == 0) sol[M[e.p]] = 1;
			else {
				line l = *s.begin();
				if(l.pR == e.p) sol[M[e.p]] = 1;
				s.erase(s.find(e.l));
			}
		}
	}
	
	for(int i = 0;i < n;i++) 
		if(sol[i] == 1) ans.pb(i);
	
	printf("%d\n", (int)ans.size());
	for(int i : ans) printf("%d ", i + 1);
	printf("\n");
	return 0;
}

Compilation message (stderr)

circuit.cpp: In function 'int main()':
circuit.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
circuit.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d%d", X + i, Y + i), M[{X[i], Y[i]}] = i, P[i] = {X[i], Y[i]};
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 100