#include using namespace std; #define int long long #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define REP(i,a) FOR(i,0,(a)-1) #define PB push_back #define EB emplace_back #define ALL(a) (a).begin(),(a).end() #define ST first #define ND second #define SIZE(a) (int)(a).size() typedef pair PII; typedef vector VI; typedef vector VII; set otoczka, res; void licz_otoczke(VII v) { auto best = v[0]; int nr_best = 0; REP(i, SIZE(v)) { if (v[i] < best) { best = v[i]; nr_best = i; } } swap(v[nr_best], v.back()); v.pop_back(); sort(v.begin(), v.end(), [&](const PII& a, const PII& b) { int ax = a.ST - best.ST; int ay = a.ND - best.ND; int bx = b.ST - best.ST; int by = b.ND - best.ND; return ax * by < ay * bx; }); VII otoczk = {best, v[0]}; auto ok = [](const PII&a, const PII& b, const PII& c) { auto x = PII(a.ST - b.ST, a.ND - b.ND); auto y = PII(c.ST - b.ST, c.ND - b.ND); return x.ST * y.ND < x.ND * y.ST; }; FOR(i, 1, SIZE(v) - 1) { while (SIZE(otoczk) > 1 && !ok(v[i], otoczk[SIZE(otoczk) - 1], otoczk[SIZE(otoczk) - 2])) { otoczk.pop_back(); } otoczk.push_back(v[i]); } otoczka = set(ALL(otoczk)); } void sortuj_katowo(VII v, PII best) { REP(i, SIZE(v) - 1) if (v[i] == best) { swap(v[i], v.back()); break; } v.pop_back(); sort(v.begin(), v.end(), [&](const PII& a, const PII& b) { int ax = a.ST - best.ST; int ay = a.ND - best.ND; int bx = b.ST - best.ST; int by = b.ND - best.ND; return ax * by < ay * bx; }); auto lewy = v[0]; bool dodano = false; FOR(i, 1, SIZE(v) - 1) { if (otoczka.find(v[i]) != otoczka.end()) { if (dodano) { res.insert(v[i]); res.insert(lewy); } dodano = false; lewy = v[i]; } else { dodano = true; res.insert(v[i]); } } } #undef int int main() { int n; cin >> n; VII v; REP(i, n) { int x, y; cin >> x >> y; v.EB(x, y); } licz_otoczke(v); if (SIZE(otoczka) == n) { cout << 3 << " " << n - 2 << " " << n << "\n"; return 0; } PII best; REP(i, SIZE(v)) if(otoczka.find(v[i]) != otoczka.end()) { best = v[i]; break; } sortuj_katowo(v, best); cout << 4 << " " << n - SIZE(otoczka) << " " << SIZE(res) + 1 << "\n"; return 0; }