QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#870745#8620. Jigsaw Puzzleucup-team987#RE 0ms3968kbC++205.4kb2025-01-25 17:35:532025-01-25 17:35:57

Judging History

你现在查看的是最新测评结果

  • [2025-01-25 17:35:57]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3968kb
  • [2025-01-25 17:35:53]
  • 提交

answer

#if __INCLUDE_LEVEL__ == 0

#include __BASE_FILE__

using kactl::P;

void Solve() {
  int n;
  IN(n);

  vector<int> sz(n);
  vector<vector<P>> p(n);
  for (int i : Rep(0, n)) {
    IN(sz[i]);
    p[i].reserve(sz[i] + 1);
    p[i].resize(sz[i]);
    for (auto& [x, y] : p[i]) {
      IN(x, y);
    }
    p[i].push_back(p[i][0]);
  }

  vector<tuple<double, int, int>> v;
  for (int i : Rep(0, n)) {
    for (int t : Rep(0, sz[i])) {
      v.emplace_back((p[i][t + 1] - p[i][t]).dist(), i, t);
    }
  }
  ranges::sort(v);

  vector<vector<pair<int, int>>> to(n);
  for (int i : Rep(0, n)) {
    to[i].assign(sz[i], {-1, -1});
  }

  constexpr double EPS = 1e-11;
  for (int vi : Rep(1, Sz(v))) {
    const auto& [d1, i1, t1] = v[vi - 1];
    const auto& [d2, i2, t2] = v[vi];
    if (d2 - d1 < EPS) {
      to[i1][t1] = {i2, t2};
      to[i2][t2] = {i1, t1};
    }
  }

  vector<vector<P>> ans(n);
  for (int i : Rep(0, n)) {
    ans[i].resize(sz[i]);
  }

  int si = -1;
  int st = -1;
  for (int i : Rep(0, n)) {
    for (int t : Rep(0, sz[i])) {
      if (to[i][t].first == -1 && to[i][Mod(t - 1, sz[i])].first == -1) {
        si = i;
        st = t;
        break;
      }
    }
    if (si != -1) {
      break;
    }
  }

  vector<bool> done(n);
  auto Go = [&](int i, int t, const P& q0, const P& q1) {
    const P& p0 = p[i][t];
    const P& p1 = p[i][t + 1];
    for (int t : Rep(0, sz[i])) {
      ans[i][t] = kactl::linearTransformation(p0, p1, q0, q1, p[i][t]);
    }
    done[i] = true;
  };

  Go(si, st, P(0, 0), P((p[si][st + 1] - p[si][st]).dist(), 0));

  vector<int> q{si};
  for (int qi = 0; qi < Sz(q); ++qi) {
    int i = q[qi];
    for (int t : Rep(0, sz[i])) {
      if (to[i][t].first == -1) {
        continue;
      }
      const auto& [i2, t2] = to[i][t];
      if (!done[i2]) {
        Go(i2, t2, ans[i][Mod(t + 1, sz[i])], ans[i][t]);
        q.push_back(i2);
      }
    }
  }

  for (int i : Rep(0, n)) {
    for (const auto& [x, y] : ans[i]) {
      OUT(clamp(x, 0.0, 1.0), clamp(y, 0.0, 1.0));
    }
    OUT();
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(DBL_DECIMAL_DIG);

  Solve();
}

#elif __INCLUDE_LEVEL__ == 1

#include <bits/stdc++.h>

template <class T> concept Range = std::ranges::range<T> && !std::convertible_to<T, std::string_view>;
template <class T> concept Tuple = std::__is_tuple_like<T>::value && !Range<T>;

namespace std {

istream& operator>>(istream& is, Range auto&& r) {
  for (auto&& e : r) is >> e;
  return is;
}
istream& operator>>(istream& is, Tuple auto&& t) {
  apply([&](auto&... xs) { (is >> ... >> xs); }, t);
  return is;
}

ostream& operator<<(ostream& os, Range auto&& r) {
  auto sep = "";
  for (auto&& e : r) os << exchange(sep, " ") << e;
  return os;
}
ostream& operator<<(ostream& os, Tuple auto&& t) {
  auto sep = "";
  apply([&](auto&... xs) { ((os << exchange(sep, " ") << xs), ...); }, t);
  return os;
}

}  // namespace std

using namespace std;

// https://github.com/kth-competitive-programming/kactl
namespace kactl {

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template <class T>
struct Point {
  typedef Point P;
  T x, y;
  explicit Point(T x = 0, T y = 0) : x(x), y(y) {}
  bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y); }
  bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); }
  P operator+(P p) const { return P(x + p.x, y + p.y); }
  P operator-(P p) const { return P(x - p.x, y - p.y); }
  P operator*(T d) const { return P(x * d, y * d); }
  P operator/(T d) const { return P(x / d, y / d); }
  T dot(P p) const { return x * p.x + y * p.y; }
  T cross(P p) const { return x * p.y - y * p.x; }
  T cross(P a, P b) const { return (a - *this).cross(b - *this); }
  T dist2() const { return x * x + y * y; }
  double dist() const { return sqrt((double)dist2()); }
  double angle() const { return atan2(y, x); }
  P unit() const { return *this / dist(); }
  P perp() const { return P(-y, x); }
  P normal() const { return perp().unit(); }
  P rotate(double a) const {
    return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
  }
  friend ostream& operator<<(ostream& os, P p) {
    return os << "(" << p.x << "," << p.y << ")";
  }
};

typedef Point<double> P;
P linearTransformation(const P& p0, const P& p1,
                       const P& q0, const P& q1, const P& r) {
  P dp = p1 - p0, dq = q1 - q0, num(dp.cross(dq), dp.dot(dq));
  return q0 + P((r - p0).cross(num), (r - p0).dot(num)) / dp.dist2();
}

}  // namespace kactl

#define LAMBDA2(x, y, ...) ([&](auto&& x, auto&& y) -> decltype(auto) { return __VA_ARGS__; })
#define LAMBDA3(x, y, z, ...) ([&](auto&& x, auto&& y, auto&& z) -> decltype(auto) { return __VA_ARGS__; })
#define Rep(...) [](int l, int r) { return views::iota(min(l, r), r); }(__VA_ARGS__)
#define Sz(r) int(size(r))
#define DivFloor(...) LAMBDA2(x, y, x / y - ((x ^ y) < 0 && x % y != 0))(__VA_ARGS__)
#define Floor(...) LAMBDA3(x, m, r, DivFloor(x - r, m) * m + r)(__VA_ARGS__)
#define Mod(...) LAMBDA2(x, m, x - Floor(x, m, 0))(__VA_ARGS__)
#define IN(...) (cin >> forward_as_tuple(__VA_ARGS__))
#define OUT(...) (cout << forward_as_tuple(__VA_ARGS__) << '\n')

#endif  // __INCLUDE_LEVEL__ == 1

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3968kb

input:

4
4
0.440405375916 0.778474079786
0.000000000000 0.090337001520
0.469097990019 0.000000000000
0.702887505082 0.689470121906
4
0.222810526978 0.000000000000
0.270828246634 0.522212063829
0.000000000000 0.547114887265
0.021480010612 0.069880870008
4
0.000000000000 0.312825941471
0.358219176380 0.00000...

output:

0.27716163632404389 0
0.47326243136115248 0.79311664451453445
2.8242961071728698e-12 0.72802924828228388
0 0

0.52441504651755244 0.999999999997775
3.8961114761062298e-12 1
2.8242961071728698e-12 0.72802924828228388
0.47326243136115242 0.79311664451453445

1 0.99999999999695455
0.52441504651624071 0...

result:

ok OK

Test #2:

score: -100
Runtime Error

input:

2
4
1.187724454426 0.260257896229
0.903481480651 1.219010174901
0.000000000000 0.951153431795
0.309873903757 0.000000000000
4
0.516015116935 0.888042716318
0.000000000000 0.031046166652
0.048574738349 0.000000000000
0.587115596943 0.842599396881

output:


result: