Submission #95475

#TimeUsernameProblemLanguageResultExecution timeMemory
95475forestryksPrinted Circuit Board (CEOI12_circuit)C++14
85 / 100
48 ms6700 KiB
/////////////////////////////////////////////////////////////////////////////////////////////// #include <bits/stdc++.h> using namespace std; #define int long long #define mp make_pair #define pb push_back #define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define FILE_IO(x) freopen((string(x) + ".in").c_str(), "r", stdin); freopen((string(x) + ".out").c_str(), "w", stdout) #define f first #define s second #define x1 x1qwer #define y1 y1qwer #define right right123 #define left left123 #define foreach(it, v) for (auto it : v) #define rep(it, n) for (int it = 0; it < n; ++it) #define forin(it, l, r) for (int it = l; it < r; ++it) #define all(x) x.begin(), x.end() typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const double DINF = numeric_limits<double>::infinity(); const ll MOD = 1e9 + 7; const double EPS = 1e-7; ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } mt19937 mmtw_(MOD); uniform_int_distribution<ll> rd_; ll randomll() { return rd_(mmtw_);} ll rnd(ll x, ll y) { return rd_(mmtw_) % (y - x + 1) + x; } //////////////////////////////////////////////////////////////////////////////////////////////// struct pt { int x, y; int id; }; inline bool operator==(const pt &a, const pt &b) { return a.x == b.x && a.y == b.y; } inline pt operator-(const pt &a) { return {-a.x, -a.y}; } inline pt operator-(const pt &a, const pt &b) { return {a.x - b.x, a.y - b.y}; } inline ll dot(const pt &a, const pt &b) { return 1LL * a.x * b.x + 1LL * a.y * b.y; } inline ll cross(const pt &a, const pt &b) { return 1LL * a.x * b.y - 1LL * a.y * b.x; } inline ll dd0(const pt &a) { return dot(a, a); } const int MAXN = 1e5 + 5; int n; pt a[MAXN]; bool used[MAXN]; int ord[MAXN]; inline int md(int x) { if (x >= n) return x - n; if (x < 0) return x + n; return x; } int findLowest() { int s = 0; for (int i = 0; i < n; ++i) { ll cr = cross(a[i], a[s] - a[i]); if (cr > 0 || (cr == 0 && dd0(a[i]) < dd0(a[s]))) { s = i; } } return s; } int findHighest() { int t = 0; for (int i = 0; i < n; ++i) { ll cr = cross(a[i], a[t] - a[i]); if (cr < 0 || (cr == 0 && dd0(a[i]) < dd0(a[t]))) { t = i; } } return t; } struct cmp { bool operator()(int i, int j) { if (i == j) return false; if (cross(a[i], a[j]) <= 0) { return cross(a[j + 1] - a[j], a[i] - a[j]) > 0; } else { return cross(a[i + 1] - a[i], a[j] - a[i]) < 0; } } }; signed main() { FAST_IO; cin >> n; rep(i, n) { cin >> a[i].x >> a[i].y; a[i].id = i + 1; } assert(n > 2); int lowest = findLowest(); if (cross(a[md(lowest - 1)] - a[lowest], a[md(lowest + 1)] - a[lowest]) < 0) { reverse(a, a + n); } rotate(a, a + findLowest(), a + n); n = findHighest() + 1; for (int i = 0; i < n; ++i) { ord[i] = i; } sort(ord, ord + n, [](int i, int j){ int cr = cross(a[i], a[j]); if (cr != 0) return cr > 0; return dd0(a[i]) < dd0(a[j]); }); vector<int> res; set<int, cmp> s; for (int ii = 0; ii < n; ++ii) { int i = ord[ii]; bool add = (i + 1 < n && cross(a[i], a[i + 1] - a[i]) > 0); if (used[i]) { s.erase(s.find(i - 1)); } if (!s.empty()) { int f = *s.begin(); if (cross(a[f + 1] - a[f], a[i] - a[f]) > 0) res.push_back(a[i].id); } else { res.push_back(a[i].id); } if (add) { s.insert(i); used[i + 1] = true; } } sort(all(res)); cout << res.size() << '\n'; for (auto it : res) { cout << it << ' '; } cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...