QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#874476 | #8620. Jigsaw Puzzle | ucup-team6275 | Compile Error | / | / | C++20 | 5.1kb | 2025-01-28 06:46:55 | 2025-01-28 06:46:56 |
Judging History
answer
#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <iomanip>
#include <map>
#include <deque>
#include <set>
#include <cassert>
#include <cmath>
#include <complex>
using namespace std;
#define ld float128_t
#define cmpl complex<ld>
struct vec {
ld x, y;
ld len() {
return sqrt(x * x + y * y);
}
vec() {}
vec(ld x, ld y) : x(x), y(y) {}
};
vec operator-(const vec& a, const vec& b) {
return {a.x - b.x, a.y - b.y};
}
vec operator+(const vec& a, const vec& b) {
return {a.x + b.x, a.y + b.y};
}
ld operator*(const vec& a, const vec& b) {
return a.x * b.x + a.y * b.y;
}
struct Side {
ld len;
int num;
int ind;
};
bool cmp(const Side& a, const Side& b) {
return a.len < b.len;
}
const ld EPS = 1e-9;
void transform_to_point(vector <vec>& a, int ind, vec flex) {
vec adding = flex - a[ind];
for (auto& i : a) {
i = i + adding;
}
}
void transform_mul(vector <vec>& a, int ind, cmpl value) {
int n = a.size();
vector <vec> flex(n);
for (int i = 0; i < n; ++i) {
int ii = (i + 1) % n;
flex[i] = (a[ii] - a[i]);
}
for (int it = 0; it < n - 1; ++it) {
int i = (ind + it) % n;
int ii = (i + 1) % n;
cmpl xd = {flex[i].x, flex[i].y};
xd *= value;
a[ii] = a[i] + vec(xd.real(), xd.imag());
}
}
bool validate(vector <vec>& a) {
for (auto i : a) {
if (i.x < -EPS || i.y < -EPS || i.x > 1 + EPS || i.y > 1 + EPS) return false;
}
return true;
}
void solve() {
int n;
cin >> n;
vector <vector <vec>> a(n);
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
a[i].resize(k);
for (int j = 0; j < k; ++j) {
cin >> a[i][j].x >> a[i][j].y;
}
}
vector <Side> sides;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < a[i].size(); ++j) {
int jj = (j + 1) % a[i].size();
ld flex = (a[i][jj] - a[i][j]).len();
if (abs(flex - 1) < EPS) continue;
sides.push_back({flex, i, j});
}
}
sort(sides.begin(), sides.end(), cmp);
map <pair <int, int>, vector <pair <int, int>>> g;
for (int i = 0; i + 1 < sides.size(); ++i) {
if (sides[i + 1].len - sides[i].len < EPS) {
pair <int, int> t1 = {sides[i].num, sides[i].ind};
pair <int, int> t2 = {sides[i + 1].num, sides[i + 1].ind};
g[t1].push_back(t2);
g[t2].push_back(t1);
}
}
vector <int> used(n);
vector <int> st;
for (int i = 0; i < n; ++i) {
int ln = a[i].size();
for (int j = 0; j < a[i].size(); ++j) {
vec vec1 = (a[i][(j + 1) % ln] - a[i][j]);
vec vec2 = a[i][j] - (a[i][(j + ln - 1) % ln]);
if (abs(vec1 * vec2) < EPS) {
used[i] = 1;
cmpl cha = {vec1.x, vec1.y};
cha /= vec1.len();
transform_mul(a[i], j, (cmpl)1 / cha);
transform_to_point(a[i], j, vec(0, 0));
used[i] = 1;
st.push_back(i);
assert(validate(a[i]));
break;
}
}
if (!st.empty()) break;
}
while (!st.empty()) {
int v = st.back();
st.pop_back();
int ln = a[v].size();
for (int i = 0; i < ln; ++i) {
int ii = (i + 1) % ln;
for (auto [vv, j] : g[make_pair(v, i)]) {
if (used[vv]) continue;
auto cop = a[vv];
vec vec1 = (a[v][ii] - a[v][i]);
int jj = (j + 1) % a[vv].size();
vec vec2 = (a[vv][jj] - a[vv][j]);
cmpl need_vec = -cmpl(vec1.x, vec1.y) / cmpl(vec2.x, vec2.y);
transform_mul(a[vv], j, need_vec);
transform_to_point(a[vv], j, a[v][ii]);
if (!validate(a[vv])) {
a[vv] = cop;
continue;
}
used[vv] = 1;
st.push_back(vv);
}
}
}
for (int i = 0; i < n; ++i) {
for (auto j : a[i]) {
cout << fixed << setprecision(10) << j.x << " " << j.y << "\n";
}
cout << "\n";
}
}
signed main() {
if (1) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
}
int32_t t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
/*
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.000000000000
0.532830100286 0.122181578260
0.088431750275 0.414089758021
4
0.158867722074 0.061734605990
0.973532298476 0.000000000000
0.853551564066 0.712811281737
0.000000000000 0.569141075980
*/
Details
answer.code:15:12: error: ‘float128_t’ does not name a type; did you mean ‘float_t’? 15 | #define ld float128_t | ^~~~~~~~~~ answer.code:19:5: note: in expansion of macro ‘ld’ 19 | ld x, y; | ^~ answer.code:15:12: error: ‘float128_t’ does not name a type; did you mean ‘float_t’? 15 | #define ld float128_t | ^~~~~~~~~~ answer.code:21:5: note: in expansion of macro ‘ld’ 21 | ld len() { | ^~ answer.code:27:12: error: expected ‘)’ before ‘x’ 27 | vec(ld x, ld y) : x(x), y(y) {} | ~ ^ answer.code: In function ‘vec operator-(const vec&, const vec&)’: answer.code:31:15: error: ‘const struct vec’ has no member named ‘x’ 31 | return {a.x - b.x, a.y - b.y}; | ^ answer.code:31:21: error: ‘const struct vec’ has no member named ‘x’ 31 | return {a.x - b.x, a.y - b.y}; | ^ answer.code:31:26: error: ‘const struct vec’ has no member named ‘y’ 31 | return {a.x - b.x, a.y - b.y}; | ^ answer.code:31:32: error: ‘const struct vec’ has no member named ‘y’ 31 | return {a.x - b.x, a.y - b.y}; | ^ answer.code:31:33: error: could not convert ‘{<expression error>, <expression error>}’ from ‘<brace-enclosed initializer list>’ to ‘vec’ 31 | return {a.x - b.x, a.y - b.y}; | ^ | | | <brace-enclosed initializer list> answer.code: In function ‘vec operator+(const vec&, const vec&)’: answer.code:35:15: error: ‘const struct vec’ has no member named ‘x’ 35 | return {a.x + b.x, a.y + b.y}; | ^ answer.code:35:21: error: ‘const struct vec’ has no member named ‘x’ 35 | return {a.x + b.x, a.y + b.y}; | ^ answer.code:35:26: error: ‘const struct vec’ has no member named ‘y’ 35 | return {a.x + b.x, a.y + b.y}; | ^ answer.code:35:32: error: ‘const struct vec’ has no member named ‘y’ 35 | return {a.x + b.x, a.y + b.y}; | ^ answer.code:35:33: error: could not convert ‘{<expression error>, <expression error>}’ from ‘<brace-enclosed initializer list>’ to ‘vec’ 35 | return {a.x + b.x, a.y + b.y}; | ^ | | | <brace-enclosed initializer list> answer.code: At global scope: answer.code:15:12: error: ‘float128_t’ does not name a type; did you mean ‘float_t’? 15 | #define ld float128_t | ^~~~~~~~~~ answer.code:38:1: note: in expansion of macro ‘ld’ 38 | ld operator*(const vec& a, const vec& b) { | ^~ answer.code:15:12: error: ‘float128_t’ does not name a type; did you mean ‘float_t’? 15 | #define ld float128_t | ^~~~~~~~~~ answer.code:43:5: note: in expansion of macro ‘ld’ 43 | ld len; | ^~ answer.code: In function ‘bool cmp(const Side&, const Side&)’: answer.code:49:14: error: ‘const struct Side’ has no member named ‘len’ 49 | return a.len < b.len; | ^~~ answer.code:49:22: error: ‘const struct Side’ has no member named ‘len’ 49 | return a.len < b.len; | ^~~ answer.code: At global scope: answer.code:15:12: error: ‘float128_t’ does not name a type; did you mean ‘float_t’? 15 | #define ld float128_t | ^~~~~~~~~~ answer.code:52:7: note: in expansion of macro ‘ld’ 52 | const ld EPS = 1e-9; | ^~ answer.code:15:12: error: ‘float128_t’ was not declared in this scope; did you mean ‘float_t’? 15 | #define ld float128_t | ^~~~~~~~~~ answer.code:16:22: note: in expansion of macro ‘ld’ 16 | #define cmpl complex<ld> | ^~ answer.code:61:46: note: in expansion of macro ‘cmpl’ 61 | void transform_mul(vector <vec>& a, int ind, cmpl value) { | ^~~~ answer.code:16:24: error: template argument 1 is invalid 16 | #define cmpl complex<ld> | ^ answer.code:61:46: note: in expansion of macro ‘cmpl’ 61 | void transform_mul(vector <vec>& a, int ind, cmpl value) { | ^~~~ answer.code: In function ‘void transform_mul(std::vector<vec>&, int, int)’: answer.code:15:12: error: ‘float128_t’ was not declared in this scope; did you mean ‘float_t’? 15 | #define ld float128_t | ^~~~~~~~~~ answer.code:16:22: note: in expansion of macro ‘ld’ 16 | #define cmpl complex<ld> | ^~ answer.code:75:9: note: in expansion of macro ‘cmpl’ 75 | cmpl xd = {flex[i].x, flex[i].y}; | ^~~~ answer.code:16:24: error: template argument 1 is invalid 16 | #define cmpl complex<ld> | ...