QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#874469 | #8620. Jigsaw Puzzle | ucup-team6275 | WA | 1ms | 4096kb | C++20 | 4.7kb | 2025-01-28 06:38:44 | 2025-01-28 06:38:44 |
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 long double
#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-12;
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());
}
}
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);
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;
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]);
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
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.2771616363 0.0000000000 0.4732624314 0.7931166445 0.0000000000 0.7280292483 0.0000000000 0.0000000000 0.5244150465 1.0000000000 0.0000000000 1.0000000000 0.0000000000 0.7280292483 0.4732624314 0.7931166445 1.0000000000 1.0000000000 0.5244150465 1.0000000000 0.4732624314 0.7931166445 1.0000000000...
result:
ok OK
Test #2:
score: 0
Accepted
time: 0ms
memory: 4096kb
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:
0.0000000000 0.0000000000 1.0000000000 -0.0000000000 1.0000000000 0.9423513255 0.0000000000 0.9156176942 0.0000000000 0.9156176942 1.0000000000 0.9423513255 1.0000000000 1.0000000000 0.0000000000 1.0000000000
result:
ok OK
Test #3:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
2 4 0.010984487654 0.637154242202 0.000000000000 0.364429379044 0.986132728982 0.000000000000 1.010174362438 0.596910060881 4 1.051085498217 0.708750184397 0.000000000000 0.686709156365 0.238826458657 0.000000000000 1.183335588457 0.328485165151
output:
0.0000000000 0.0000000000 0.2729459836 0.0000000000 0.5973940248 1.0000000000 0.0000000000 1.0000000000 0.5973940248 1.0000000000 0.2729459836 0.0000000000 1.0000000000 0.0000000000 1.0000000000 1.0000000000
result:
ok OK
Test #4:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
2 4 0.826904615568 0.393527743434 0.397181437913 1.296488423966 0.078224855062 1.144695506210 0.000000000000 0.000000000000 4 1.022875732881 0.126407334306 0.000000000000 0.646188215994 0.027327732878 0.000000000000 1.026434680216 0.042252902634
output:
0.0000000000 0.0000000000 1.0000000000 -0.0000000000 1.0000000000 0.3532341881 0.0000000000 0.9157703468 0.0000000000 0.9157703468 1.0000000000 0.3532341881 1.0000000000 1.0000000000 0.0000000000 1.0000000000
result:
ok OK
Test #5:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
2 4 0.341358383182 1.391325004482 0.000000000000 0.397880525310 0.531982366752 0.000000000000 1.130916074772 0.800798609763 4 1.051975365355 0.325235570274 0.003475133323 0.261167306728 0.000000000000 0.247567137365 0.968870740861 0.000000000000
output:
1.0000000000 0.9859628650 -0.0000000000 0.6643147981 0.0000000000 0.0000000000 1.0000000000 0.0000000000 -0.0000000000 0.6643147981 1.0000000000 0.9859628650 1.0000000000 1.0000000000 0.0000000000 1.0000000000
result:
ok OK
Test #6:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
2 4 0.082220615826 0.000000000000 0.226158368535 0.989676141653 0.157074587283 1.000663841224 0.000000000000 0.013077098690 4 0.796463091415 0.000000000000 1.301438005407 0.863236513506 0.516366280506 1.336613199533 0.000000000000 0.480245367141
output:
1.0000000000 0.0832540700 -0.0000000000 0.0699521149 0.0000000000 0.0000000000 1.0000000000 0.0000000000 -0.0000000000 0.0699521149 1.0000000000 0.0832540700 1.0000000000 1.0000000000 -0.0000000000 1.0000000000
result:
ok OK
Test #7:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
2 4 0.919168715346 1.052156329422 0.000000000000 0.740689700679 0.930075742206 0.000000000000 1.240100800584 0.105054119170 4 1.147942957461 0.000000000000 1.169807209495 0.019794683310 0.498656378683 0.761115506098 0.000000000000 0.309659628218
output:
0.0000000000 0.0000000000 0.9705063565 0.0000000000 0.3273406556 1.0000000000 0.0000000000 1.0000000000 0.9705063565 0.0000000000 1.0000000000 0.0000000000 1.0000000000 1.0000000000 0.3273406556 1.0000000000
result:
ok OK
Test #8:
score: 0
Accepted
time: 1ms
memory: 4096kb
input:
3 4 0.000000000000 0.136914050437 1.205473860654 0.000000000000 1.271801552152 0.076389603324 0.516716328492 0.732016253949 4 0.193356841190 1.008675084911 0.000000000000 0.998661755544 0.051717482677 0.000000000000 0.069051074671 0.000897651020 4 0.189612940043 1.009339071474 0.000000000000 0.01178...
output:
1.0000000000 0.7881258762 -0.0000000000 0.1011668629 0.0000000000 0.0000000000 1.0000000000 0.0000000000 1.0000000000 0.8063840533 1.0000000000 1.0000000000 -0.0000000000 1.0000000000 -0.0000000000 0.9826431803 1.0000000000 0.8063840533 -0.0000000000 0.9826431803 -0.0000000000 0.1011668629 1.00000...
result:
ok OK
Test #9:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
4 5 0.933026549197 0.034096050827 1.030580221284 0.341877704707 0.077317792660 0.644021283449 0.000000000000 0.400083791499 0.816713028753 0.000000000000 5 0.000000000000 0.567232254210 0.177744443744 0.000000000000 0.278219549927 0.015709015317 0.955605106642 0.861917658609 0.954247706440 0.8662495...
output:
0.0000000000 0.3228719025 0.0000000000 0.0000000000 1.0000000000 -0.0000000000 1.0000000000 0.2558975206 0.1005754062 0.3905177700 0.0000000000 1.0000000000 0.0000000000 0.4055712679 0.1005754062 0.3905177700 1.0000000000 0.9954604619 1.0000000000 1.0000000000 1.0000000000 0.9954604619 0.100575406...
result:
ok OK
Test #10:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
4 4 0.578470606282 0.000000000000 1.060885700639 0.240610189702 0.817167310798 0.691089665380 0.000000000000 0.248985836080 4 0.000000000000 0.520597380570 0.022799149709 0.000000000000 0.882566155159 0.037652814638 0.461438543132 0.525442723877 4 0.057126159280 0.427841981239 0.000000000000 0.38584...
output:
0.5387913306 0.4942519038 -0.0000000000 0.5121820102 0.0000000000 0.0000000000 0.9290953717 0.0000000000 1.0000000000 0.4789036232 1.0000000000 1.0000000000 0.1394089019 1.0000000000 0.5387913306 0.4942519038 0.9290953717 0.0000000000 1.0000000000 -0.0000000000 1.0000000000 0.4789036232 0.53879133...
result:
ok OK
Test #11:
score: -100
Wrong Answer
time: 1ms
memory: 3968kb
input:
3 3 0.823899373670 0.782629779690 0.288601744213 0.945945553033 0.000000000000 0.000000000000 5 0.919151534064 0.575061183684 0.169973459288 1.263242535288 0.000000000000 1.135836341471 0.145355826013 0.008808731413 0.151958544733 0.000000000000 4 1.000848179486 0.040130744019 0.991701546880 0.26786...
output:
-0.0000000000 0.5596566750 0.0000000000 0.0000000000 0.9889913832 -0.0000000000 0.9191515341 0.5750611837 0.1699734593 1.2632425353 0.0000000000 1.1358363415 0.1453558260 0.0088087314 0.1519585447 0.0000000000 1.0008481795 0.0401307440 0.9917015469 0.2678679725 0.0000000000 0.0411756649 0.00165374...
result:
wrong answer Double parameter [name=y] equals to 1.26324, violates the range [-1e-06, 1]