Submission #95479

#TimeUsernameProblemLanguageResultExecution timeMemory
95479forestryksPrinted Circuit Board (CEOI12_circuit)C++14
95 / 100
118 ms7160 KiB
#pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,sse4") /** * Author: Sergey Kopeliovich ([email protected]) */ #define VERSION "0.1.5" #include <cassert> #include <cstdio> #include <algorithm> /** Fast allocation */ #define FAST_ALLOCATOR_MEMORY (1024*1024*20) #ifdef FAST_ALLOCATOR_MEMORY int allocator_pos = 0; char allocator_memory[(int)FAST_ALLOCATOR_MEMORY]; inline void * operator new ( size_t n ) { char *res = allocator_memory + allocator_pos; allocator_pos += n; assert(allocator_pos <= (int)FAST_ALLOCATOR_MEMORY); return (void *)res; } inline void operator delete ( void * ) noexcept { } //inline void * operator new [] ( size_t ) { assert(0); } //inline void operator delete [] ( void * ) { assert(0); } #endif /** Fast input-output */ template <class T = int> inline T readInt(); inline double readDouble(); inline int readUInt(); inline int readChar(); // first non-blank character inline void readWord( char *s ); inline bool readLine( char *s ); // do not save '\n' inline bool isEof(); inline int getChar(); inline int peekChar(); inline bool seekEof(); inline void skipBlanks(); template <class T> inline void writeInt( T x, char end = 0, int len = -1 ); inline void writeChar( int x ); inline void writeWord( const char *s ); inline void writeDouble( double x, int len = 0 ); inline void flush(); static struct buffer_flusher_t { ~buffer_flusher_t() { flush(); } } buffer_flusher; /** Read */ static const int buf_size = 4096; static unsigned char buf[buf_size]; static int buf_len = 0, buf_pos = 0; inline bool isEof() { if (buf_pos == buf_len) { buf_pos = 0, buf_len = fread(buf, 1, buf_size, stdin); if (buf_pos == buf_len) return 1; } return 0; } inline int getChar() { return isEof() ? -1 : buf[buf_pos++]; } inline int peekChar() { return isEof() ? -1 : buf[buf_pos]; } inline bool seekEof() { int c; while ((c = peekChar()) != -1 && c <= 32) buf_pos++; return c == -1; } inline void skipBlanks() { while (!isEof() && buf[buf_pos] <= 32U) buf_pos++; } inline int readChar() { int c = getChar(); while (c != -1 && c <= 32) c = getChar(); return c; } inline int readUInt() { int c = readChar(), x = 0; while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar(); return x; } template <class T> inline T readInt() { int s = 1, c = readChar(); T x = 0; if (c == '-') s = -1, c = getChar(); else if (c == '+') c = getChar(); while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar(); return s == 1 ? x : -x; } inline double readDouble() { int s = 1, c = readChar(); double x = 0; if (c == '-') s = -1, c = getChar(); while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar(); if (c == '.') { c = getChar(); double coef = 1; while ('0' <= c && c <= '9') x += (c - '0') * (coef *= 1e-1), c = getChar(); } return s == 1 ? x : -x; } inline void readWord( char *s ) { int c = readChar(); while (c > 32) *s++ = c, c = getChar(); *s = 0; } inline bool readLine( char *s ) { int c = getChar(); while (c != '\n' && c != -1) *s++ = c, c = getChar(); *s = 0; return c != -1; } /** Write */ static int write_buf_pos = 0; static char write_buf[buf_size]; inline void writeChar( int x ) { if (write_buf_pos == buf_size) fwrite(write_buf, 1, buf_size, stdout), write_buf_pos = 0; write_buf[write_buf_pos++] = x; } inline void flush() { if (write_buf_pos) { fwrite(write_buf, 1, write_buf_pos, stdout), write_buf_pos = 0; fflush(stdout); } } template <class T> inline void writeInt( T x, char end, int output_len ) { if (x < 0) writeChar('-'), x = -x; char s[24]; int n = 0; while (x || !n) s[n++] = '0' + x % 10, x /= 10; while (n < output_len) s[n++] = '0'; while (n--) writeChar(s[n]); if (end) writeChar(end); } inline void writeWord( const char *s ) { while (*s) writeChar(*s++); } inline void writeDouble( double x, int output_len ) { if (x < 0) writeChar('-'), x = -x; int t = (int)x; writeInt(t), x -= t; writeChar('.'); for (int i = output_len - 1; i > 0; i--) { x *= 10; t = std::min(9, (int)x); writeChar('0' + t), x -= t; } x *= 10; t = std::min(9, (int)(x + 0.5)); writeChar('0' + t); } /////////////////////////////////////////////////////////////////////////////////////////////// #include <bits/stdc++.h> using namespace std; #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 = 2e5 + 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; n = readInt(); rep(i, n) { // cin >> a[i].x >> a[i].y; a[i].x = readInt(); a[i].y = readInt(); 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){ ll 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'; writeInt(res.size(), '\n'); for (auto it : res) { // cout << it << ' '; writeInt(it, ' '); } // cout << '\n'; writeChar('\n'); }
#Verdict Execution timeMemoryGrader output
Fetching results...