#include #include #include using namespace std; using ll = long long; struct pont { int x, y; int id; bool kb = false; bool klikkben = false; }; int sgn(ll x) { return x > 0 ? 1 : x < 0 ? -1 : 0; } int fordul(ll Ax, ll Ay, ll Bx, ll By) { return sgn(Ax * By - Ay * Bx); } int fordul(const pont& A, const pont& O, const pont& B) { return fordul(A.x - O.x, A.y - O.y, B.x - O.x, B.y - O.y); } vector kburok(vector& pontok) { auto xyr = [](const pont& p1, const pont& p2) { return make_pair(p1.x, p1.y) < make_pair(p2.x, p2.y); }; auto minit = min_element(pontok.begin(), pontok.end(), xyr); swap(*minit, *pontok.begin()); pont O = pontok[0]; auto fr = [O](const pont& A, const pont& B) {return fordul(A, O, B) == 1;}; sort(pontok.begin() + 1, pontok.end(), fr); vector kb; kb.push_back(&pontok[0]); kb.push_back(&pontok[1]); for(int i = 2; i < pontok.size(); i++) { while(fordul(*kb[kb.size() - 2], *kb[kb.size() - 1], pontok[i]) >= 0) { kb.pop_back(); } kb.push_back(&pontok[i]); } return kb; } void forgat(vector& pontok) { auto idr = [](pont* p1, pont* p2) {return p1->id < p2->id;}; rotate(pontok.begin(), min_element(pontok.begin(), pontok.end(), idr), pontok.end()); } void megold(vector& kb, vector& belso) { if(kb.size() == 3) { if(belso.size()) { for(pont* p : kb) { p->klikkben = true; } } return; } forgat(kb); int szemkozti = kb.size() / 2; if(kb[szemkozti]->id < kb[(kb.size() + 1)/2]->id) { szemkozti++; } vector kb1, kb2, belso1, belso2; for(int i = 0; i <= szemkozti; i++) { kb1.push_back(kb[i]); } kb2.push_back(kb[0]); for(int i = szemkozti; i < kb.size(); i++) { kb2.push_back(kb[i]); } pont* A = kb[0]; pont* B = kb[szemkozti]; for(pont* p : belso) { if(fordul(*A, *B, *p) == 1) { belso1.push_back(p); } else { belso2.push_back(p); } } megold(kb1, belso1); megold(kb2, belso2); } int main() { ios::sync_with_stdio(false); int N; cin >> N; vector pontok(N); for(int i = 0; i < N; i++) { cin >> pontok[i].x >> pontok[i].y; pontok[i].id = i; } vector kb = kburok(pontok); for(pont* p : kb) { p->kb = true; } vector belso; for(pont& p : pontok) { if(!p.kb) belso.push_back(&p); } bool vb = belso.size() != 0; cout << 3 + vb << " "; cout << (vb ? belso.size() : N - 2) << " "; if(vb) { megold(kb, belso); int er = 0; for(pont* p : kb) { if(p->klikkben) er++; } cout << er + belso.size() << "\n"; } else { cout << N << "\n"; } }