結果

問題 No.2179 Planet Traveler
ユーザー 👑 emthrmemthrm
提出日時 2023-01-06 23:04:10
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 39 ms / 3,000 ms
コード長 9,278 bytes
コンパイル時間 2,621 ms
コンパイル使用メモリ 229,600 KB
実行使用メモリ 8,576 KB
最終ジャッジ日時 2024-11-30 19:45:56
合計ジャッジ時間 3,799 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 1 ms
6,820 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 1 ms
6,820 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 2 ms
6,820 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 2 ms
6,820 KB
testcase_10 AC 2 ms
6,816 KB
testcase_11 AC 7 ms
8,320 KB
testcase_12 AC 10 ms
8,320 KB
testcase_13 AC 10 ms
8,320 KB
testcase_14 AC 30 ms
8,576 KB
testcase_15 AC 39 ms
8,576 KB
testcase_16 AC 36 ms
8,320 KB
testcase_17 AC 32 ms
8,320 KB
testcase_18 AC 30 ms
8,320 KB
testcase_19 AC 16 ms
8,320 KB
testcase_20 AC 5 ms
6,816 KB
testcase_21 AC 32 ms
8,064 KB
testcase_22 AC 20 ms
6,820 KB
testcase_23 AC 8 ms
6,820 KB
testcase_24 AC 23 ms
7,296 KB
testcase_25 AC 12 ms
6,816 KB
testcase_26 AC 11 ms
7,680 KB
testcase_27 AC 4 ms
6,816 KB
testcase_28 AC 9 ms
6,820 KB
testcase_29 AC 32 ms
7,296 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 998244353;
// constexpr int MOD = 1000000007;
constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1};
constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1};
constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U>
inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U>
inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << fixed << setprecision(20);
  }
} iosetup;

namespace geometry {

using Integer = long long;

int sgn(const Integer x) {
  return x > 0 ? 1 : (x < 0 ? -1 : 0);
}

struct Point {
  Integer x, y;
  explicit Point(const Integer x = 0, const Integer y = 0) : x(x), y(y) {}
  Integer norm() const { return x * x + y * y; }
  Point& operator+=(const Point& p) {
    x += p.x; y += p.y;
    return *this;
  }
  Point& operator-=(const Point& p) {
    x -= p.x; y -= p.y;
    return *this;
  }
  Point& operator*=(const Integer k) {
    x *= k; y *= k;
    return *this;
  }
  Point& operator/=(const Integer k) {
    x /= k; y /= k;
    return *this;
  }
  bool operator<(const Point& p) const {
    const int x_sgn = sgn(p.x - x);
    return x_sgn != 0 ? x_sgn == 1 : sgn(p.y - y) == 1;
  }
  bool operator<=(const Point& p) const { return !(p < *this); }
  bool operator>(const Point& p) const { return p < *this; }
  bool operator>=(const Point& p) const { return !(*this < p); }
  Point operator+() const { return *this; }
  Point operator-() const { return Point(-x, -y); }
  Point operator+(const Point& p) const { return Point(*this) += p; }
  Point operator-(const Point& p) const { return Point(*this) -= p; }
  Point operator*(const Integer k) const { return Point(*this) *= k; }
  Point operator/(const Integer k) const { return Point(*this) /= k; }
  friend std::ostream& operator<<(std::ostream& os, const Point& p) {
    return os << '(' << p.x << ", " << p.y << ')';
  }
  friend std::istream& operator>>(std::istream& is, Point& p) {
    Integer x, y; is >> x >> y;
    p = Point(x, y);
    return is;
  }
};

struct Segment {
  Point s, t;
  explicit Segment(const Point& s = Point(0, 0), const Point& t = Point(0, 0))
      : s(s), t(t) {}
};
struct Line : Segment {
  using Segment::Segment;
};

struct Circle {
  Point p; Integer r;
  explicit Circle(const Point& p = Point(0, 0), const Integer r = 0)
      : p(p), r(r) {}
};

Integer cross(const Point& a, const Point& b) { return a.x * b.y - a.y * b.x; }
Integer dot(const Point& a, const Point& b) { return a.x * b.x + a.y * b.y; }

int ccw(const Point& a, const Point& b, const Point& c) {
  const Point ab = b - a, ac = c - a;
  const int sign = sgn(cross(ab, ac));
  if (sign == 0) {
    if (sgn(dot(ab, ac)) == -1) return 2;
    if (sgn(ac.norm() - ab.norm()) == 1) return -2;
  }
  return sign;
}

Integer closest_pair(std::vector<Point> ps) {
  const int n = ps.size();
  assert(n >= 2);
  std::sort(ps.begin(), ps.end());
  const std::function<Integer(int, int)> f =
      [&ps, &f](const int left, const int right) -> Integer {
        const int mid = (left + right) >> 1;
        Integer x_mid = ps[mid].x, d = std::numeric_limits<Integer>::max();
        if (left + 1 < mid) d = std::min(d, f(left, mid));
        if (mid + 1 < right) d = std::min(d, f(mid, right));
        std::inplace_merge(std::next(ps.begin(), left),
                           std::next(ps.begin(), mid),
                           std::next(ps.begin(), right),
                           [](const Point& a, const Point& b) -> bool {
                             return sgn(b.y - a.y) == 1;
                           });
        std::vector<Point> tmp;
        for (int i = left; i < right; ++i) {
          if (sgn((ps[i].x - x_mid) * (ps[i].x - x_mid) - d) == 1) continue;
          for (int j = static_cast<int>(tmp.size()) - 1; j >= 0; --j) {
            const Point v = ps[i] - tmp[j];
            if (sgn(v.y * v.y - d) == 1) break;
            d = std::min(d, v.norm());
          }
          tmp.emplace_back(ps[i]);
        }
        return d;
      };
  return f(0, n);
}

bool is_parallel(const Segment& a, const Segment& b) {
  return sgn(cross(a.t - a.s, b.t - b.s)) == 0;
}
bool is_orthogonal(const Segment& a, const Segment& b) {
  return sgn(dot(a.t - a.s, b.t - b.s)) == 0;
}

int common_tangent_num(const Circle&, const Circle&);
bool has_intersected(const Segment& a, const Point& b) {
  return ccw(a.s, a.t, b) == 0;
}
bool has_intersected(const Segment& a, const Segment& b) {
  return ccw(a.s, a.t, b.s) * ccw(a.s, a.t, b.t) <= 0 &&
         ccw(b.s, b.t, a.s) * ccw(b.s, b.t, a.t) <= 0;
}
bool has_intersected(const Line& a, const Point& b) {
  const int c = ccw(a.s, a.t, b);
  return c != 1 && c != -1;
}
bool has_intersected(const Line& a, const Segment& b) {
  return ccw(a.s, a.t, b.s) * ccw(a.s, a.t, b.t) != 1;
}
bool has_intersected(const Line& a, const Line& b) {
  return sgn(cross(a.t - a.s, b.t - b.s)) != 0 ||
         sgn(cross(a.t - a.s, b.s - a.s)) == 0;
}
bool has_intersected(const Circle& a, const Point& b) {
  return (a.p - b).norm() == a.r * a.r;
}
bool has_intersected(const Circle& a, const Circle& b) {
  const int num = common_tangent_num(a, b);
  return 1 <= num && num <= 3;
}

int common_tangent_num(const Circle& a, const Circle& b) {
  const Integer dist = (a.p - b.p).norm();
  int sign = sgn((a.r + b.r) * (a.r + b.r) - dist);
  if (sign == -1) return 4;
  if (sign == 0) return 3;
  sign = sgn((b.r - a.r) * (b.r - a.r) - dist);
  if (sign == -1) return 2;
  if (sign == 0) return 1;
  return 0;
}

using Polygon = std::vector<Point>;

Integer area(Polygon a) {
  const int n = a.size();
  a.resize(n + 1);
  a.back() = a.front();
  Integer res = 0;
  for (int i = 0; i < n; ++i) {
    res += cross(a[i], a[i + 1]);
  }
  // return res / 2;
  return res;
}

int contains(Polygon a, const Point &b) {
  const int n = a.size();
  a.resize(n + 1);
  a.back() = a.front();
  bool is_in = false;
  for (int i = 0; i < n; ++i) {
    Point p = a[i] - b, q = a[i + 1] - b;
    if (sgn(q.y - p.y) == -1) std::swap(p, q);
    const int sign = sgn(cross(p, q));
    if (sign == 1 && sgn(p.y) != 1 && sgn(q.y) == 1) is_in = !is_in;
    if (sign == 0 && sgn(dot(p, q)) != 1) return 1;
  }
  return is_in ? 2 : 0;
}

bool is_convex(Polygon a) {
  const int n = a.size();
  a.resize(n + 2);
  a[n] = a[0];
  a[n + 1] = a[1];
  for (int i = 1; i <= n; ++i) {
    if (ccw(a[i - 1], a[i], a[i + 1]) == -1) return false;
  }
  return true;
}

Polygon monotone_chain(std::vector<Point> ps, const bool is_tight = true) {
  const int n = ps.size();
  std::sort(ps.begin(), ps.end());
  Polygon convex_hull(n << 1);
  int idx = 0;
  for (int i = 0; i < n; convex_hull[idx++] = ps[i++]) {
    while (idx >= 2 &&
           sgn(cross(convex_hull[idx - 1] - convex_hull[idx - 2],
                     ps[i] - convex_hull[idx - 1])) < is_tight) {
      --idx;
    }
  }
  for (int i = n - 2, border = idx + 1; i >= 0; convex_hull[idx++] = ps[i--]) {
    while (idx >= border &&
           sgn(cross(convex_hull[idx - 1] - convex_hull[idx - 2],
                     ps[i] - convex_hull[idx - 1])) < is_tight) {
      --idx;
    }
  }
  convex_hull.resize(idx - 1);
  return convex_hull;
}

std::pair<Point, Point> rotating_calipers(Polygon a) {
  const int n = a.size();
  if (n <= 2) {
    assert(n == 2);
    return {a[0], a[1]};
  }
  a.resize(n + 1);
  a.back() = a.front();
  int high = 0, low = 0;
  for (int i = 1; i < n; ++i) {
    if (a[i].y > a[high].y) high = i;
    if (a[i].y < a[low].y) low = i;
  }
  Integer max_norm = (a[high] - a[low]).norm();
  int i = high, j = low, argmax_i = i, argmax_j = j;
  do {
    int* i_or_j = &(sgn(cross(a[i + 1] - a[i], a[j + 1] - a[j])) != -1 ? j : i);
    if (++(*i_or_j) == n) *i_or_j = 0;
    const Integer tmp = (a[j] - a[i]).norm();
    if (sgn(tmp - max_norm) == 1) {
      max_norm = tmp;
      argmax_i = i; argmax_j = j;
    }
  } while (i != high || j != low);
  return {a[argmax_i], a[argmax_j]};
}

}  // namespace geometry

int main() {
  using namespace geometry;
  int n; cin >> n;
  vector<Point> p;
  p.reserve(n);
  vector<int> t(n);
  REP(i, n) cin >> p[i] >> t[i];
  vector dist(n, vector(n, 0LL));
  REP(i, n) FOR(j, i + 1, n) {
    dist[i][j] = dist[j][i] = (t[i] == t[j] ? (p[i] - p[j]).norm() : llround(ceill(p[i].norm() + p[j].norm() - 2 * sqrtl(p[i].norm() * p[j].norm()))));
  }
  ll lb = -1, ub = dist[0][n - 1];
  while (ub - lb > 1) {
    const ll mid = (lb + ub) / 2;
    vector<int> can_reach(n, false);
    can_reach[0] = true;
    queue<int> que({0});
    while (!que.empty()) {
      const int star = que.front(); que.pop();
      REP(i, n) {
        if (!can_reach[i] && dist[star][i] <= mid) {
          can_reach[i] = true;
          que.emplace(i);
        }
      }
    }
    (can_reach[n - 1] ? ub : lb) = mid;
  }
  cout << ub << '\n';
  return 0;
}
0