Submission #68891

#	Time	Username	Problem	Language	Result	Execution time	Memory
68891		ainta	Printed Circuit Board (CEOI12_circuit)	C++17	85 / 100	160 ms	31132 KiB

circuit

#include<stdio.h>
#include<algorithm>
using namespace std;
struct point {
	long long x, y;
	int c;
	bool operator <(const point &p)const {
		return x*p.y != y*p.x ? x*p.y<y*p.x : x<p.x;
	}
}w[200001];
struct point2 {
	int x, y;
}P[200001];
struct vector2 {
	double x, y;
	int c;
}w2[200001], t1, t2, t3;
double X1, X2, Y1, Y2, tt;
int r[400001], N, i, c, sz, IT2[600001];
bool v[400001];
double IT[600001], INF = 1e9;
double F(double x, double y) {
	tt = (Y2*x - X2*y) / ((X1 - X2)*y - (Y1 - Y2)*x);
	return Y1*tt + Y2*(1 - tt);
}
bool ccw() {
	return (t2.x - t1.x)*(t3.y - t1.y) - (t2.y - t1.y)*(t3.x - t1.x)<0;
}
void Do(int b, int e, int k) {
	int s = b - sz, l = e - sz, t = 1;
	double tp;
	if (k == 8999) {
		k = k;
	}
	while (b <= e) {
		if (b & 1) {
			tp = F(w2[s].x, w2[s].y);
			if (tp<IT[b])IT[b] = tp, IT2[b] = k;
			else if (tp == IT[b]) {
				t1.y = tp; t1.x = tp*(double)w2[s].x / w2[s].y;
				t2.x = P[IT2[b]].x, t2.y = P[IT2[b]].y;
				if (t1.y != P[k].y)t3.x = P[k].x, t3.y = P[k].y;
				else t3.x = P[k + 1].x, t3.y = P[k + 1].y;
				if (ccw())IT2[b] = k;
			}
		}
		if (!(e & 1)) {
			tp = F(w2[l - t + 1].x, w2[l - t + 1].y);
			if (tp<IT[e])IT[e] = tp, IT2[e] = i;
			else if (tp == IT[e]) {
				t1.y = tp; t1.x = tp*(double)w2[l - t + 1].x / w2[l - t + 1].y;
				t2.x = P[IT2[e]].x, t2.y = P[IT2[e]].y;
				if (t1.y != P[k].y)t3.x = P[k].x, t3.y = P[k].y;
				else t3.x = P[k + 1].x, t3.y = P[k + 1].y;
				if (ccw())IT2[e] = k;
			}
		}
		if (b & 1)s += t;
		if (!(e & 1))l -= t;
		t <<= 1;
		b = (b + 1) >> 1, e = (e - 1) >> 1;
	}
}
void DFS(int s, int z, int a, int b) {
	int tt = s;
	if (s >= c)return;
	if (s == 0) {
		if (a >= sz)return;
		tt = 1;
	}
	if (b == -1 && IT[a] != INF)b = IT2[a];
	else if (IT[a] != INF) {
		X1 = P[b].x, X2 = P[b + 1].x, Y1 = P[b].y, Y2 = P[b + 1].y;
		if (F(w2[tt].x, w2[tt].y)>IT[a])b = IT2[a];
	}
	if (a >= sz) {
		if (a - sz >= 1 && a - sz<c)IT2[a] = b;
		return;
	}
	DFS(s, z >> 1, a << 1, b);
	DFS(s + z, z >> 1, (a << 1) + 1, b);
}
bool Pos(int a) {
	if (abs(a) == N - 1)return true;
	return a<0 ? false : a>1 ? false : true;
}
int main()
{
	scanf("%d", &N);
	for (i = 0; i<N; i++) {
		scanf("%d%d", &P[i].x, &P[i].y);
		w[i].x = P[i].x, w[i].y = P[i].y, w[i].c = i;
	}
	P[N] = P[0];
	sort(w, w + N);
	for (i = 0; i<N; i++) {
		c++;
		if (i && w[i].x*w[i - 1].y == w[i].y*w[i - 1].x)c--;
		else w2[c].x = w[i].x, w2[c].y = w[i].y, w2[c].c = w[i].c;
		r[w[i].c] = c;
	}
	r[N] = r[0];
	sz = 1;
	while (sz <= c)sz *= 2;
	for (i = 1; i<sz * 2; i++)IT[i] = INF;
	for (i = 0; i<N; i++) {
		if (r[i] == r[i + 1])continue;
		X1 = P[i].x, Y1 = P[i].y, X2 = P[i + 1].x, Y2 = P[i + 1].y;
		Do(sz + min(r[i], r[i + 1]), sz + max(r[i], r[i + 1]) - 1, i);
	}
	DFS(0, sz >> 1, 1, -1);
	v[w2[1].c] = v[w2[c].c] = true;
	for (i = 1; i<c - 1; i++) {
		if (Pos(w2[i + 1].c - IT2[sz + i]) || Pos(w2[i + 1].c - IT2[sz + i + 1]))v[w2[i + 1].c] = true;
	}
	c = 0;
	for (i = 0; i<N; i++) {
		if (v[i])c++;
	}
	printf("%d\n", c);
	for (i = 0; i<N; i++)if (v[i])printf("%d ", i + 1);
}

Compilation message (stderr)

circuit.cpp: In function 'int main()':
circuit.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
circuit.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &P[i].x, &P[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 85 / 100