#ifndef LOCAL #pragma GCC optimize("O3") #endif #include using namespace std; #define sim template muu & operator<<( #define ris return *this #define eni(r) sim> typename enable_if <1 r sizeof(dud(0)),muu&>::type operator<<(c g) { sim> struct rge {c b,e ;}; sim> rge range(c i, c j) {return rge{i, j};} sim> auto dud(c *r)-> decltype(cerr << *r); sim> char dud(...); struct muu { #ifdef LOCAL stringstream a; ~muu() {cerr << a.str() << endl;} eni(<) a << boolalpha << g; ris;} eni(==) ris << range(begin(g), end(g));} sim, class m mor pair r) {ris << "(" << r.first << ", " << r.second << ")";} sim mor rge u) { a << "["; for (c i = u.b; i != u.e; ++i) *this << ", " + 2 * (i == u.b) << *i; ris << "]"; } #else sim mor const c&) {ris;} #endif muu & operator()(){ris;} }; #define debug (muu() << __FUNCTION__ << "#" << __LINE__ << ": ") #define imie(r) "[" #r ": " << (r) << "] " #define imask(r) "[" #r ": " << bitset<8 * sizeof(r)>(r) << "] " #define arr(a, i) "[" #a imie(i) ": " << a[i] << "] " #define arr2(a, i, j) "[" #a imie(i) imie(j) ": " << a[i][j] << "] " using ll = long long; const int N = 1e5 + 7; int n; pair tab[N]; bool naoto[N]; bool pokryty[N]; pair operator-(pair a, pair b) { return make_pair(a.first - b.first, a.second - b.second); } ll ilwek(pair a, pair b) { return 1ll * a.first * b.second - 1ll * a.second * b.first; } vector convexHull() { vector kol; for (int i = 1; i <= n; ++i) kol.push_back(i); sort (kol.begin(), kol.end(), [](int a, int b) -> bool { return tab[a] < tab[b]; }); vector res1; for (int it = 0; it < n; ++it) { int u = kol[it]; while ((int) res1.size() >= 2) { int sz = res1.size(); if (ilwek(tab[u] - tab[res1[sz - 2]], tab[res1[sz - 1]] - tab[res1[sz - 2]]) > 0) break; res1.pop_back(); } res1.push_back(u); } vector res2; for (int it = n - 1; it >= 0; --it) { int u = kol[it]; while ((int) res2.size() >= 2) { int sz = res2.size(); if (ilwek(tab[u] - tab[res2[sz - 2]], tab[res2[sz - 1]] - tab[res2[sz - 2]]) > 0) break; res2.pop_back(); } res2.push_back(u); } res1.pop_back(); res2.pop_back(); res1.insert(res1.end(), res2.begin(), res2.end()); return res1; } void f(vector oto, vector sro) { debug << imie(oto) imie(sro); if (oto.size() == 3) { if (!sro.empty()) for (int u : oto) pokryty[u] = true; return; } pair gd = {n + 1, 0}; for (int it = 0; it < (int) oto.size(); ++it) { gd = min(gd, {oto[it], it}); } int len = oto.size(); int x = gd.second; int y = (x + (len / 2)) % len; int ile = 1 + (len / 2); if (len % 2 == 1) { if (oto[(y + 1) % len] < oto[y]) { y = (y + 1) % len; ile++; } } vector otol, otor; vector srol, sror; for (int it = 0; it < ile; ++it) { otol.push_back(oto[(x + it) % len]); } ile = len + 2 - ile; for (int it = 0; it < ile; ++it) { otor.push_back(oto[(y + it) % len]); } for (int u : sro) { if (ilwek(tab[u] - tab[oto[x]], tab[oto[y]] - tab[oto[x]]) < 0) srol.push_back(u); else sror.push_back(u); } f(otol, srol); f(otor, sror); } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d %d", &tab[i].first, &tab[i].second); vector ch = convexHull(); debug << imie(ch); vector sr; for (int u : ch) naoto[u] = true; for (int i = 1; i <= n; ++i) { if (!naoto[i]) { sr.push_back(i); pokryty[i] = true; } } f(ch, sr); int ilePokrytych = 0; for (int i = 1; i <= n; ++i) ilePokrytych += pokryty[i]; if (ilePokrytych == 0) { printf("3 %d %d\n", n - 2, n); } else { printf("4 %d %d\n", (int) sr.size(), ilePokrytych); } return 0; }