답안 #951094

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
951094 2024-03-21T06:38:01 Z vjudge1 Printed Circuit Board (CEOI12_circuit) C++17
95 / 100
31 ms 6860 KB
#include <iostream>
#include <algorithm>
#include <vector>

typedef long long ll;
const int LEN = 200'001;

struct Pos {
	ll x, y;
	int i;
	ll s() const { return x * x + y * y; }
	bool operator<(const Pos& r) const { return y * r.x < r.y * x; }
	bool operator==(const Pos& r) const { return y * r.x == r.y * x; }
	friend std::istream& operator>>(std::istream& is, Pos& p) { is >> p.x >> p.y; return is; }
} O = { 0, 0 }, p[LEN];
ll cross(const Pos& p1, const Pos& p2, const Pos& p3) { return (p2.x - p1.x) * (p3.y - p2.y) - (p2.y - p1.y) * (p3.x - p2.x); }
ll ccw(const Pos& p1, const Pos& p2, const Pos& p3) {
	ll ret = cross(p1, p2, p3);
	return ret < 0 ? -1 : !!ret;
}

bool invisible(const Pos& p1, const Pos& p2, const Pos& t) {
	return ccw(O, p1, t) <= 0 && ccw(O, p2, t) >= 0 && ccw(p1, p2, t) >= 0;
}

int N, L, R;

int main() {
	std::cin.tie(0)->sync_with_stdio(0);
	std::cin >> N >> p[0];
	
	p[0].i = 1;
	ll area = 0;
	for (int i = 1; i < N; ++i) {
		std::cin >> p[i];
		p[i].i = i + 1;
		area += cross(O, p[i - 1], p[i]);
	}
	area += cross(O, p[N - 1], p[0]);
	if (area > 0) std::reverse(p, p + N);
	for (int i = 1; i < N; ++i) {
		if (p[L] < p[i] || p[i] == p[L] && p[i].s() < p[L].s()) L = i;
		if (p[i] < p[R] || p[i] == p[R] && p[i].s() < p[R].s()) R = i;
	}
	std::rotate(p, p + R, p + N);
	L = (L - R + N) % N;

	// std::cout << R << ' ' << L << '\n';
	// std::cout << p[0].i << ' ' << p[L].i << '\n';

	std::vector<int> stack; // monotonic, ccw order
	stack.push_back(0);
	if (L > 1) stack.push_back(1);
	
	for (int i = 2, fv = -1, bv = -1, cw = 0; i <= L; ++i) {
		// j -> i
		ll dir = cross(O, p[i - 1], p[i]);
		ll ccw = cross(p[i - 2], p[i - 1], p[i]);

		if (!~fv && !~bv) {
			if (dir < 0) { // cw
				if (!cw && ccw < 0) {
					cw = 1;
					fv = i - 1;
					continue;
				}
				cw = 1;
				while (stack.size() && invisible(p[i - 1], p[i], p[stack.back()])) stack.pop_back();
			}
			else if (dir == 0) {
				if (p[i].s() < p[i - 1].s()) {
					if (stack.back() == i - 1) stack.pop_back();
				}
			}
			else if (dir > 0) { // ccw
				if (cw && ccw > 0) {
					cw = 0;
					bv = i - 1;
					continue;
				}
				cw = 0;
			}
			if (stack.empty() || p[stack.back()] < p[i]) stack.push_back(i);
		}
		else if (~fv) {
			if (p[fv] < p[i]) {
				cw = 0;
				fv = -1;
				stack.push_back(i);
			}
		}
		else if (~bv) {
			if (p[i] < p[bv]) {
				cw = 1;
				bv = -1;
				while (stack.size() && invisible(p[i - 1], p[i], p[stack.back()])) stack.pop_back();
				if (stack.empty() || p[stack.back()] < p[i]) stack.push_back(i);
			}
		}
	}

	std::vector<int> ret;
	for (const int& i : stack) ret.push_back(p[i].i);
	std::sort(ret.begin(), ret.end());
	std::cout << ret.size() << '\n';
	for (const int& i : ret) std::cout << i << ' ';
}

Compilation message

circuit.cpp: In function 'int main()':
circuit.cpp:42:35: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   42 |   if (p[L] < p[i] || p[i] == p[L] && p[i].s() < p[L].s()) L = i;
      |                      ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
circuit.cpp:43:35: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   43 |   if (p[i] < p[R] || p[i] == p[R] && p[i].s() < p[R].s()) R = i;
      |                      ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Correct 1 ms 500 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 3 ms 2648 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 4 ms 2908 KB Output is correct
8 Correct 3 ms 2652 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 3 ms 2652 KB Output is correct
13 Correct 5 ms 2936 KB Output is correct
14 Correct 7 ms 3160 KB Output is correct
15 Correct 6 ms 3172 KB Output is correct
16 Correct 15 ms 5468 KB Output is correct
17 Correct 16 ms 5724 KB Output is correct
18 Correct 26 ms 6748 KB Output is correct
19 Correct 31 ms 6860 KB Output is correct
20 Correct 28 ms 6740 KB Output is correct