/** * CERC 2018 * Problem Solution: Incredible Hull * Idea: Find convex hull + detect empty triangles by sorting points by polar angle * @author Josef Malik */ #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int ll; typedef pair pii; #define PB push_back #define MP make_pair #define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++) #define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--) #define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--) #define R1(a) do{scanf("%d", &(a));}while(0) #define R2(a, b) do{scanf("%d%d", &(a), &(b));}while(0) #define R3(a, b, c) do{scanf("%d%d%d", &(a), &(b), &(c));}while(0) #define SV(vec) do{int s_v_;scanf("%d", &(s_v_));vec.PB(s_v_);}while(0) #define MM(co, cim) memset((co), (cim), sizeof((co))) #define DEB(x) cerr << ">>> " << #x << " : " << x << endl; #define INF 1000000007 struct point { point () : x(0), y(0) {} point (ll X, ll Y) : x(X), y(Y) {} ll x, y; int val; bool operator < (const point & p) const { if (x != p.x) return x < p.x; return y < p.y; } }; ll cross (const point & p0, const point & p1, const point & p2) { return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x); } vector convex_hull (vector P) { vector R(2 * P.size() + 14); int K = 0; sort(P.begin(), P.end()); for (int i = 0; i < P.size(); i++) { while (K >= 2 && cross(R[K - 2], R[K - 1], P[i]) <= 0) K--; R[K++] = P[i]; } for (int i = P.size() - 2, T = K + 1; i >= 0; i--) { while (K >= T && cross(R[K - 2], R[K - 1], P[i]) <= 0) K--; R[K++] = P[i]; } R.resize(K); R.pop_back(); return R; } point pivot; ll ccw (point a, point b, point c) { ll area = cross(a, b, c); if (area > 0) return -1; else if (area < 0) return 1; return 0; } ll sqr_dist (point a, point b) { ll dx = a.x - b.x, dy = a.y - b.y; return dx * dx + dy * dy; } bool polar_ordering (point a, point b) { ll order = ccw(pivot, a, b); if (order == 0) { return sqr_dist(pivot, a) < sqr_dist(pivot, b); } return (order == -1); } int n, x, y; vector pts; set respts, chpts; int main () { R1(n); FOR(i, 0, n) { R2(x, y); point Q = point(x, y); Q.val = i; pts.PB(Q); } vector ch = convex_hull(pts); if (ch.size() == pts.size()) printf("3 %d %d\n", n - 2, n); else { int mval = INF; FOR(i, 0, ch.size()) { mval = min(mval, ch[i].val); chpts.insert(ch[i]); } swap(pts[0], pts[mval]); pivot = pts[0]; sort(pts.begin() + 1, pts.end(), polar_ordering); respts.insert(pts[0]); int canch; canch = 1; do { int pin, nxtp; pin = 0; nxtp = canch + 1; while (nxtp < n && !chpts.count(pts[nxtp])) { ++pin; ++nxtp; } if (pin) { respts.insert(pts[canch]); respts.insert(pts[nxtp]); } canch = nxtp; } while (canch < n); FOR(i, 0, pts.size()) { if (!chpts.count(pts[i])) respts.insert(pts[i]); } printf("4 %d %d\n", n - chpts.size(), respts.size()); } return 0; }