QOJ.ac

QOJ

详细

Extra Test:

Wrong Answer
time: 1ms
memory: 3840kb

input:

5
3 -6 2
-5 6 2
-5 6 1
-7 -2 2
4 9 2

output:

not a penguin

result:

wrong answer 1st lines differ - expected: 'probably', found: 'not a penguin'

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#890059#9049. Machine Learning with PenguinsHoMaMaOvO (Riku Kawasaki, Masaki Nishimoto, Yui Hosaka)WA 36ms9092kbC++145.8kb2025-02-08 19:53:232025-02-15 21:11:12

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


inline int sig(Int r) { return (r < 0) ? -1 : (r > 0) ? +1 : 0; }
inline Int sq(Int r) { return r * r; }
struct Pt {
  Int x, y;
  Pt() : x(0), y(0) {}
  Pt(Int x_, Int y_) : x(x_), y(y_) {}
  Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y); }
  Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y); }
  Pt operator*(const Pt &a) const { return Pt(x * a.x - y * a.y, x * a.y + y * a.x); }
  Pt operator+() const { return Pt(+x, +y); }
  Pt operator-() const { return Pt(-x, -y); }
  Pt operator*(const Int &k) const { return Pt(x * k, y * k); }
  Pt operator/(const Int &k) const { return Pt(x / k, y / k); }
  friend Pt operator*(const Int &k, const Pt &a) { return Pt(k * a.x, k * a.y); }
  Pt &operator+=(const Pt &a) { x += a.x; y += a.y; return *this; }
  Pt &operator-=(const Pt &a) { x -= a.x; y -= a.y; return *this; }
  Pt &operator*=(const Pt &a) { return *this = *this * a; }
  Pt &operator*=(const Int &k) { x *= k; y *= k; return *this; }
  Pt &operator/=(const Int &k) { x /= k; y /= k; return *this; }
  Int abs2() const { return x * x + y * y; }
  Int dot(const Pt &a) const { return x * a.x + y * a.y; }
  Int det(const Pt &a) const { return x * a.y - y * a.x; }
  bool operator==(const Pt &a) const { return (x == a.x && y == a.y); }
  bool operator!=(const Pt &a) const { return !(x == a.x && y == a.y); }
  bool operator<(const Pt &a) const { return ((x != a.x) ? (x < a.x) : (y < a.y)); }
  friend ostream &operator<<(ostream &os, const Pt &a) { os << "(" << a.x << ", " << a.y << ")"; return os; }
};
inline Int tri(const Pt &a, const Pt &b, const Pt &c) { return (b - a).det(c - a); }

// [0, 2 PI)
int cmpArg(const Pt &a, const Pt &b) {
  const int sa = (a.y > 0) ? 1 : (a.y < 0) ? 3 : (a.x > 0) ? 0 : 2;
  const int sb = (b.y > 0) ? 1 : (b.y < 0) ? 3 : (b.x > 0) ? 0 : 2;
  return (sa < sb) ? -1 : (sa > sb) ? +1 : sig(b.det(a));
}

// Watch out for the case a == b.
int iSP(const Pt &a, const Pt &b, const Pt &c) {
  int s = sig((b - a).det(c - a));
  if (s) return s;
  if (sig((b - a).dot(c - a)) < 0) return -2; // c-a-b
  if (sig((a - b).dot(c - b)) < 0) return +2; //   a-b-c
  return 0;
}

// radius(circle abc)^2 - dist(circle abc, d)^2
// +: inside, 0: boundary, -: outside
__int128 sCP(Pt a, Pt b, Pt c, Pt d) {
  if (tri(a, b, c) < 0) swap(b, c);
  const __int128 a2 = (a -= d).abs2();
  const __int128 b2 = (b -= d).abs2();
  const __int128 c2 = (c -= d).abs2();
  return a2 * b.det(c) + b2 * c.det(a) + c2 * a.det(b);
}


int N;
vector<Int> X, Y, Z;

bool solve() {
  const Int maxZ = *max_element(Z.begin(), Z.end());
  // P ==> boundary, Q ==> inside or boundary
  vector<Pt> P, Q;
  for (int u = 0; u < N; ++u) {
    ((0 < Z[u] && Z[u] < maxZ) ? P : Q).emplace_back(X[u], Y[u]);
  }
  sort(P.begin(), P.end());
  sort(Q.begin(), Q.end());
  P.erase(unique(P.begin(), P.end()), P.end());
  Q.erase(unique(Q.begin(), Q.end()), Q.end());
  const int PLen = P.size();
  int QLen = Q.size();
cerr<<"P = "<<P<<", Q = "<<Q<<endl;
  if (PLen == 0) {
    return true;
  } else if (PLen == 1) {
    for (int i = 0; i < QLen; ++i) {
      if (Q[i] == P[0]) {
        swap(Q[i--], Q[--QLen]);
      } else {
        Q[i] -= P[0];
      }
    }
    sort(Q.begin(), Q.end(), [&](const Pt &q0, const Pt &q1) -> bool {
      return (cmpArg(q0, q1) < 0);
    });
    bool same = true;
    for (int i = 0; i < QLen; ++i) {
      const Pt q0 = Q[i];
      const Pt q1 = Q[(i - 1 + QLen) % QLen];
      if (q0.det(q1) > 0) return true;
      same = same && (cmpArg(q0, q1) == 0);
    }
    if (same) return true;
    return false;
  } else if (PLen == 2) {
    // "farthest" from P[0]P[1]
    int cnt = 0;
    Pt qm;
    for (const Pt &q : Q) {
      const int s = iSP(P[0], P[1], q);
      if (abs(s) == 2) return false;
      if (s == -1) {
        if (cnt++) {
          if (sCP(P[0], P[1], qm, q) < 0) qm = q;
        } else {
          qm = q;
        }
      }
    }
    if (!cnt) return true;
    for (const Pt &q : Q) if (sCP(P[0], P[1], qm, q) < 0) return false;
    return true;
  } else {
    if (tri(P[0], P[1], P[2]) == 0) return false;
    for (const Pt &p : P) if (sCP(P[0], P[1], P[2], p) != 0) return false;
    for (const Pt &q : Q) if (sCP(P[0], P[1], P[2], q) < 0) return false;
    return true;
  }
}

int main() {
  for (; ~scanf("%d", &N); ) {
    X.resize(N);
    Y.resize(N);
    Z.resize(N);
    for (int i = 0; i < N; ++i) {
      scanf("%lld%lld%lld", &X[i], &Y[i], &Z[i]);
    }
    
    const bool ans = solve();
    puts(ans ? "probably" : "not a penguin");
  }
  return 0;
}