//#define _CRT_SECURE_NO_WARNINGS
//#include <iostream>
//#include <algorithm>
//#include <cmath>
//#include <cstring>
//#include <vector>
//#include <cassert>
//typedef long long ll;
//const ll INF = 1e17;
//const int LEN = 2e5 + 1;
//int N;
//bool V[LEN];
//
//struct Pos {
// int x, y, i;
// Pos(int X = 0, int Y = 0, int I = 0) : x(X), y(Y), i(I) {}
// ll operator / (const Pos& p) const { return { (ll)x * p.y - (ll)y * p.x }; }
// Pos operator - (const Pos& p) const { return { x - p.x, y - p.y }; }
// ll Euc() const { return (ll)x * x + (ll)y * y; }
// friend std::istream& operator >> (std::istream& is, Pos& p) { is >> p.x >> p.y; return is; }
// friend std::ostream& operator << (std::ostream& os, const Pos& p) { os << p.x << " " << p.y; return os; }
//}; const Pos O = { 0, 0 };
//std::vector<Pos> H;
//ll cross(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) / (d3 - d2); }
//int ccw(const Pos& d1, const Pos& d2, const Pos& d3) {
// ll ret = cross(d1, d2, d3);
// return !ret ? 0 : ret > 0 ? 1 : -1;
//}
//ll area(const std::vector<Pos>& H) {
// ll ret = 0;
// int sz = H.size();
// for (int i = 0; i < sz; i++) {
// Pos cur = H[i], nxt = H[(i + 1) % sz];
// ret += cross(O, cur, nxt);
// }
// return ret;
//}
//bool norm(std::vector<Pos>& H) {
// ll A = area(H);
// assert(A);
// if (A > 0) { std::reverse(H.begin(), H.end()); return 1; }
// return 0;
//}
//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;
//}
//std::vector<int> stack;
//void solve() {
// std::cin.tie(0)->sync_with_stdio(0);
// std::cout.tie(0);
// std::cin >> N;
// H.resize(N);
// for (int i = 0; i < N; i++) std::cin >> H[i], H[i].i = i + 1;
// norm(H);//normalize cw
//
// int r = 0, l = 0;
// for (int i = 0; i < N; i++) {
// if (H[r] / H[i] < 0 || (!(H[r] / H[i]) && H[r].Euc() > H[i].Euc())) r = i;
// if (H[l] / H[i] > 0 || (!(H[l] / H[i]) && H[l].Euc() > H[i].Euc())) l = i;
// }
// stack.clear();
// stack.push_back(r);
//
// bool fvis = 1, bvis = 1, rvs = 0;
// for (int i = r; i < r + N; i++) {
// if (i % N == l) break;
// Pos& pre = H[(i - 1 + N) % N], cur = H[i % N], nxt = H[(i + 1) % N];
// if (fvis && bvis) {
// ll DIR = cur / nxt;//ccw(O, cur, nxt);
// int CCW = ccw(pre, cur, nxt);
// if (DIR < 0) {//move backward
// if (!rvs && CCW < 0) {
// rvs = 1;
// fvis = 0;
// continue;
// }
// rvs = 1;
// while (stack.size() && invisible(cur, nxt, H[stack.back()])) stack.pop_back();
// }
// else if (!DIR) {//move vertical
// if (cur.Euc() > nxt.Euc()) {
// if (stack.size() && stack.back() == i % N) stack.pop_back();
// if (stack.size() < 1 || H[stack.back()] / nxt > 0) stack.push_back((i + 1) % N);
// }
// }
// else if (DIR > 0) {//move forward
// if (rvs && CCW > 0) {
// stack.push_back(i % N);
// rvs = 0;
// bvis = 0;
// continue;
// }
// if (stack.size() && rvs && H[stack.back()] / cur > 0) stack.push_back(i % N);
// rvs = 0;
// if (stack.size() < 1 || H[stack.back()] / nxt > 0) stack.push_back((i + 1) % N);
// }
// }
// else if (!fvis) {
// if (H[stack.back()] / nxt > 0) {
// rvs = 0;
// fvis = 1;
// stack.push_back((i + 1) % N);
// }
// }
// else if (!bvis) {
// if (H[stack.back()] / nxt < 0) {
// stack.pop_back();
// rvs = 1;
// bvis = 1;
// while (stack.size() && invisible(cur, nxt, H[stack.back()])) stack.pop_back();
// }
// }
// }
//
// memset(V, 0, sizeof V);
// for (const int& i : stack) V[H[i].i] = 1;
// std::cout << stack.size() << "\n";
// for (int i = 1; i <= N; i++) if (V[i]) std::cout << i << " ";
// return;
//}
//int main() { solve(); return 0; }//boj3303 Printed Circuit Board
#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];
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]);
}
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 = 1, 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();
if (stack.empty() || p[stack.back()] < p[i]) stack.push_back(i);
}
}
else if (dir > 0) { // ccw
if (cw && ccw > 0) {
cw = 0;
bv = i - 1;
continue;
}
if (!stack.empty() && cw && p[stack.back()] < p[i - 1]) stack.push_back(i - 1);
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:162:35: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
162 | if (p[L] < p[i] || p[i] == p[L] && p[i].s() < p[L].s()) L = i;
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
circuit.cpp:163:35: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
163 | if (p[i] < p[R] || p[i] == p[R] && p[i].s() < p[R].s()) R = i;
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
| 6 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 9 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
2684 KB |
Output isn't correct |
| 11 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 12 |
Incorrect |
3 ms |
2652 KB |
Output isn't correct |
| 13 |
Correct |
4 ms |
2652 KB |
Output is correct |
| 14 |
Incorrect |
5 ms |
2648 KB |
Output isn't correct |
| 15 |
Incorrect |
7 ms |
2652 KB |
Output isn't correct |
| 16 |
Incorrect |
15 ms |
4736 KB |
Output isn't correct |
| 17 |
Correct |
13 ms |
4700 KB |
Output is correct |
| 18 |
Incorrect |
25 ms |
4956 KB |
Output isn't correct |
| 19 |
Incorrect |
24 ms |
4984 KB |
Output isn't correct |
| 20 |
Incorrect |
26 ms |
4992 KB |
Output isn't correct |
