QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#870745 | #8620. Jigsaw Puzzle | ucup-team987# | RE | 0ms | 3968kb | C++20 | 5.4kb | 2025-01-25 17:35:53 | 2025-01-25 17:35:57 |
Judging History
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
Details
Tip: Click on the bar to expand more detailed information
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