test_d.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Point {
    long long x, y;
    bool operator<(const Point& p) const {
        if (x != p.x) return x < p.x;
        return y < p.y;
    }
    bool operator==(const Point& p) const {
        return x == p.x && y == p.y;
    }
};
long long cross(Point a, Point p, Point b) {
    return (p.x - a.x) * (b.y - a.y) - (p.y - a.y) * (b.x - a.x);
}
vector<Point> strict_hull(const vector<Point>& pts) {
    int n = pts.size();
    if (n <= 2) return pts;
    vector<Point> h(2 * n);
    int k = 0;
    for (int i = 0; i < n; i++) {
        while (k >= 2 && cross(h[k - 2], h[k - 1], pts[i]) <= 0) k--;
        h[k++] = pts[i];
    }
    for (int i = n - 2, t = k + 1; i >= 0; i--) {
        while (k >= t && cross(h[k - 2], h[k - 1], pts[i]) <= 0) k--;
        h[k++] = pts[i];
    }
    h.resize(k - 1);
    return h;
}
vector<Point> get_hull_collinear(const vector<Point>& pts) {
    int n = pts.size();
    if (n <= 2) return pts;
    vector<Point> h(2 * n);
    int k = 0;
    for (int i = 0; i < n; i++) {
        while (k >= 2 && cross(h[k - 2], h[k - 1], pts[i]) < 0) k--;
        h[k++] = pts[i];
    }
    for (int i = n - 2, t = k + 1; i >= 0; i--) {
        while (k >= t && cross(h[k - 2], h[k - 1], pts[i]) < 0) k--;
        h[k++] = pts[i];
    }
    h.resize(k - 1);
    sort(h.begin(), h.end());
    h.erase(unique(h.begin(), h.end()), h.end());
    return h;
}
int main() {
    int n; cin >> n;
    vector<Point> pts;
    for (int i = 0; i < n; i++) {
        long long x, y; cin >> x >> y;
        Point p; p.x = x; p.y = y; pts.push_back(p);
        if (y != 0) {
            Point p2; p2.x = x; p2.y = -y; pts.push_back(p2);
        }
    }
    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end()), pts.end());
    while (!pts.empty()) {
        vector<Point> h = get_hull_collinear(pts);
        vector<Point> nxt;
        std::set_difference(pts.begin(), pts.end(), h.begin(), h.end(), std::back_inserter(nxt));
        if (nxt.empty()) {
            vector<Point> sh = strict_hull(pts);
            if (sh.size() >= 3) {
                cout << "Ini Ulah Manusia\n";
            } else {
                cout << "Warning! Invasi Alien\n";
            }
            break;
        }
        pts = nxt;
    }
}