QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#870593 | #8620. Jigsaw Puzzle | ucup-team159# | RE | 1ms | 4096kb | C++20 | 4.8kb | 2025-01-25 16:58:32 | 2025-01-25 16:58:36 |
Judging History
answer
#line 1 "J.cpp"
// #pragma GCC target("avx2,avx512f,avx512vl,avx512bw,avx512dq,avx512cd,avx512vbmi,avx512vbmi2,avx512vpopcntdq,avx512bitalg,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("Ofast")
#line 2 "/home/sigma/comp/library/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define all(c) c.begin(),c.end()
#define si(x) int(x.size())
#define pb push_back
#define eb emplace_back
#define fs first
#define sc second
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T,class U> bool chmax(T& x, U y){
if(x<y){ x=y; return true; }
return false;
}
template<class T,class U> bool chmin(T& x, U y){
if(y<x){ x=y; return true; }
return false;
}
template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());}
template<class T> int lwb(const V<T>& v, const T& a){return lower_bound(all(v),a) - v.begin();}
template<class T>
V<T> Vec(size_t a) {
return V<T>(a);
}
template<class T, class... Ts>
auto Vec(size_t a, Ts... ts) {
return V<decltype(Vec<T>(ts...))>(a, Vec<T>(ts...));
}
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
o<<"{";
for(const T& v:vc) o<<v<<",";
o<<"}";
return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }
#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
void dmpr(ostream& os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
os<<t<<" ~ ";
dmpr(os,args...);
}
#define shows(...) cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__)
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {"; \
for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) void(0)
#define dump(x) void(0)
#define shows(...) void(0)
#endif
template<class D> D divFloor(D a, D b){
return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0);
}
template<class D> D divCeil(D a, D b) {
return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0);
}
#line 5 "J.cpp"
using D = long double;
using P = complex<D>;
using Pol = vector<P>;
D inf=1e50,eps=1e-10,pi=acos(D(0))*2;
bool eq(D a, D b) { return abs(a-b)<eps;}
int main(){
cin.tie(0);
ios::sync_with_stdio(false); //DON'T USE scanf/printf/puts !!
cout << fixed << setprecision(20);
int N; cin >> N;
V<Pol> pieces(N);
rep(i,N){
int M; cin >> M;
rep(j,M){
D x,y; cin >> x >> y;
pieces[i].pb(P(x,y));
}
}
V<Pol> ans(N);
queue<tuple<P,P,int>> que;
V<bool> used(N);
auto Put = [&](int i, int j, P a, P b) {
assert(!used[i]); used[i] = true;
// pieces[i] を、 j->j+1 が a->b になるように置く
auto pol = pieces[i];
int M = si(pol);
{
P diff = a - pol[j];
rep(k,M) pol[k] += diff;
P rot = (b-a)/(pol[(j+1)%M]-pol[j]);
rep(k,M) pol[k] = a + rot*(pol[k]-a);
}
ans[i] = pol;
rep(k,M) if(k != j){
P p = pol[k], q = pol[(k+1)%M];
que.push({q,p,i});
}
};
{
D cho = inf;
int ii=0, jj=0;
rep(i,N){
auto& pol = pieces[i];
int M = si(pol);
rep(j,M){
P p = pol[j], q = pol[(j+1)%M], r = pol[(j+2)%M];
D theta = arg((r-q)/(q-p));
if(abs(theta-pi/2) < abs(cho-pi/2)){
cho = theta;
ii = i;
jj = (j+1)%M;
}
}
}
show(cho*2);
D len = abs(pieces[ii][jj]-pieces[ii][(jj+1)%si(pieces[ii])]);
Put(ii,jj,P(0,0),P(len,0));
}
auto getLen = [&](int i, int j) -> D {
auto& pol = pieces[i];
int M = si(pol);
return abs(pol[j]-pol[(j+1)%M]);
};
while(si(que)){
auto [a,b,from] = que.front(); que.pop();
// outer edge
if(eq(a.real(),0) && eq(b.real(),0)) continue;
if(eq(a.real(),1) && eq(b.real(),1)) continue;
if(eq(a.imag(),0) && eq(b.imag(),0)) continue;
if(eq(a.imag(),1) && eq(b.imag(),1)) continue;
D len = abs(b-a);
D best = 1e10;
int ii = -1, jj = -1;
rep(i,N) if(i != from){
auto& pol = pieces[i];
int M = si(pol);
rep(j,M){
D len2 = getLen(i,j);
if(abs(len-len2) < abs(len-best)){
best = len2;
ii = i;
jj = j;
}
}
}
assert(eq(best,len));
if(!used[ii]) Put(ii,jj,a,b);
}
// rep(i,N) assert(used[i]);
rep(i,N){
rep(j,si(ans[i])){
D x = ans[i][j].real(), y = ans[i][j].imag();
chmax(x,0.0); chmin(x,1.0); chmax(y,0.0); chmin(y,1.0);
cout << x << " " << y << endl;
}
cout << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4096kb
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.00000000000000000000 0.72283836367552306877 0.79311664451551734797 0.52673756864208640420 0.72802924828096515428 1.00000000000000000000 0.00000000000000000000 0.99999999999973512242 0.99999999999912804314 0.47558495348664420904 0.99999999999910975054 1.00000000000000000000 0.72802924828096515428 ...
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.99999999999986212456 0.99999999999990942472 0.00000000000032707703 0.99999999999990081214 0.00000000000000000000 0.05764867448135792250 0.99999999999962680064 0.08438230583967962223 0.99999999999962680059 0.08438230583967962223 0.00000000000000000000 0.05764867448135792250 0.00000000000000000000 ...
result:
ok OK
Test #3:
score: 0
Accepted
time: 1ms
memory: 4096kb
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.00000000000001257865 1.00000000000000000000 0.00000000000000000000 0.72705401641843211150 0.99999999999953312688 0.40260597515517438443 1.00000000000000000000 0.99999999999961324665 0.99999999999953312693 0.40260597515517438437 0.00000000000000000000 0.72705401641843211150 0.00000000000000000000 ...
result:
ok OK
Test #4:
score: 0
Accepted
time: 0ms
memory: 4096kb
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.00000000000000000000 0.00000000000000000000 1.00000000000000000000 0.00000000000000000000 1.00000000000000000000 0.35323418807480485348 0.00000000000008020811 0.91577034681186199577 0.00000000000008020814 0.91577034681186199577 1.00000000000000000000 0.35323418807480485356 1.00000000000000000000 ...
result:
ok OK
Test #5:
score: 0
Accepted
time: 0ms
memory: 4096kb
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.00000000000000000000 0.98596286502522484597 0.00000000000000000000 0.66431479808598346896 0.00000000000000000000 0.00000000000000000000 1.00000000000000000000 0.00000000000000000003 0.00000000000000000000 0.66431479808598346896 1.00000000000000000000 0.98596286502522484602 1.00000000000000000000 ...
result:
ok OK
Test #6:
score: 0
Accepted
time: 1ms
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:
0.00000000000029131336 0.91674592996802356157 1.00000000000000000000 0.93004788513642270913 0.99999999999941286538 1.00000000000000000000 0.00000000000032371434 1.00000000000000000000 1.00000000000000000000 0.93004788513642270913 0.00000000000029131336 0.91674592996802356157 0.00000000000000000000 ...
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.99999999999985240409 1.00000000000000000000 0.02949364345620178265 0.99999999999986656052 0.67265934444832101071 0.00000000000000000000 0.99999999999984179615 0.00000000000069630928 0.02949364345620178265 0.99999999999986656052 0.00000000000000000000 0.99999999999935757433 0.00000000000000000000 ...
result:
ok OK
Test #8:
score: 0
Accepted
time: 0ms
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:
0.78812587621209996417 0.00000000000000000003 0.10116686293171896392 0.99999999999998505498 0.00000000000000000000 0.99999999999971401842 0.00000000000000000000 0.00000000000000000000 0.80638405334376762326 0.00000000000028370199 1.00000000000000000000 0.00000000000005557187 1.00000000000000000000 ...
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.67712809753283450989 0.00000000000000000000 1.00000000000000000000 0.00000000000000000000 1.00000000000000000000 1.00000000000000000000 0.74410247941782719589 1.00000000000000000000 0.60948222999189178228 0.10057540616233335781 0.00000000000000000000 0.00000000000000000000 0.59442873205963222801 ...
result:
ok OK
Test #10:
score: 0
Accepted
time: 1ms
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.53879133060654024469 0.49425190379509195647 0.00000000000000000000 0.51218201018174725191 0.00000000000000000000 0.00000000000000000000 0.92909537170225892040 0.00000000000000000000 0.99999999999871463870 0.47890362322883991042 0.99999999999864575559 0.99999999999891490450 0.13940890191072552939 ...
result:
ok OK
Test #11:
score: 0
Accepted
time: 1ms
memory: 4096kb
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.44034332495276633853 0.00000000000046415248 0.99999999999869927843 0.00000000000079506063 0.99999999999886167912 0.98899138320957061569 0.04120886119178140288 0.99999999999964777448 0.22792083300536547817 0.00000000000000000000 0.44034332495276633853 0.00000000000046415248 0.99999999999886167912 ...
result:
ok OK
Test #12:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
3 4 0.784316497399 0.634251077946 0.006801703755 1.263115726074 0.000000000000 1.254706245103 0.271325510967 0.000000000000 4 0.176866080715 0.000000000000 1.325780121566 0.313426050448 1.266765536888 0.366283123599 0.000000000000 0.158412084360 4 0.637108390812 0.412967145896 0.087765752860 1.24856...
output:
0.99999999999907417011 0.99999999999918165211 0.00000000000000000000 1.00000000000000000000 0.00000000000000000000 0.98918415310006274817 0.99999999999846320164 0.18425850783700377849 0.00000000000000000000 0.75174784800186549954 0.99999999999928769132 0.10503356614060338671 0.99999999999846320170 ...
result:
ok OK
Test #13:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
6 4 0.921652078321 0.149600568920 0.078937119587 0.337059477836 0.000000000000 0.296726127108 0.743849912614 0.000000000000 4 1.023501554022 0.000000000000 0.951768850516 0.475614028074 0.000000000000 0.332067057777 0.284068099668 0.057351469275 4 0.049230909949 0.111307311191 0.213550746194 0.00000...
output:
0.00000000000000012318 0.19846996273530594265 0.68599219867302534365 0.72261121045956265503 0.70595071947874910164 0.80897963916409249712 0.00000000000025530930 0.43083592485389870575 0.51900698086929417867 0.00000000000000000000 1.00000000000000000000 0.00000000000000000000 1.00000000000000000000 ...
result:
ok OK
Test #14:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
5 4 0.000000000000 0.055459913902 0.998460914583 0.000000000000 1.018410323962 0.359155002823 0.013840567536 0.304635665324 4 0.500064513905 0.019086089913 0.674971706538 0.000000000000 0.813263023860 0.224894936058 0.000000000000 0.724982740923 4 0.731666528739 0.764701825648 0.735437510038 0.80982...
output:
0.00000000000000000000 0.00000000000000000000 0.99999999999996903746 0.00000000000000000000 0.99999999999987990856 0.35970862512227875563 0.00000000000001206471 0.24955984534062548609 0.84101019204774171738 0.66062877441244796379 1.00000000000000000000 0.73598821861275638093 1.00000000000000000000 ...
result:
ok OK
Test #15:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
5 3 0.000000000000 0.061747330599 0.247806449221 0.000000000000 0.229822253050 0.275345649819 5 0.538394745273 0.029328826979 0.968971368133 0.672420034382 0.916291764826 0.738725056183 0.000000000000 0.284470622299 0.226013039857 0.000000000000 4 0.014373491307 0.145007400418 1.026752147154 0.00000...
output:
0.57219607709351807067 0.00000000000000000000 0.82757964961056901915 0.00000000000000000000 0.74355522136729114196 0.26282799250421780409 0.74355522136729114196 0.26282799250421780409 0.50788604527959591343 0.99999999999930928499 0.42320135645918703808 0.99999999999902940335 0.20887056307544143654 ...
result:
ok OK
Test #16:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
7 5 0.810317691232 0.643017535788 0.309793761559 0.764262848182 0.000000000000 0.561376089933 0.651400345497 0.000000000000 0.931962307009 0.325553870105 4 0.171076044751 0.000000000000 0.265564197304 0.103411254234 0.071756689228 0.418964516278 0.000000000000 0.156314315443 4 0.386419063825 0.00000...
output:
0.59083771974035287166 0.29939449400139211309 0.35592923722224891755 0.75769857950997946685 0.00000000000000000000 0.85992181299352714590 0.00000000000000000000 0.00000000000000000000 0.42976777053171888828 0.00000000000000000000 0.00000000000000000000 1.00000000000000000000 0.00000000000000000000 ...
result:
ok OK
Test #17:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
7 4 0.000000000000 0.177488867232 0.176950314412 0.039266481958 0.556242974263 0.000000000000 0.075309305264 0.536013509980 4 0.203281319601 0.323314306022 0.000000000000 0.110510724304 0.349283252863 0.000000000000 0.408321765666 0.043218341300 5 0.860850463389 0.099669917919 0.433724726467 0.81261...
output:
0.28972790430307402234 0.70451282499083655371 0.51078144967719839157 0.74391043454180198725 0.79331093996824365166 0.99999999999992630266 0.07316673437302319372 0.99999999999851639287 0.00000000000000000000 0.65287562175028354737 0.28972790430307402231 0.70451282499083655371 0.07316673437350486194 ...
result:
ok OK
Test #18:
score: 0
Accepted
time: 1ms
memory: 4096kb
input:
6 4 0.880095449711 0.315891170135 0.784668799664 0.890843756640 0.000000000000 0.600905379684 0.728266831893 0.000000000000 4 0.083309474403 0.000000000000 0.291032832219 0.544543596864 0.066903447530 0.393219949838 0.000000000000 0.014725970157 4 0.007778511174 0.196667909856 0.000000000000 0.13427...
output:
0.42761207634944174911 0.19436792908884265100 0.99999999999886327951 0.08460096171139009947 0.99999999999744140100 0.92112315962120807245 0.18392577277286736844 0.44627296279518234191 1.00000000000000000000 0.08460096170927490720 0.42761207634944174911 0.19436792908884265098 0.61563849835561101301 ...
result:
ok OK
Test #19:
score: 0
Accepted
time: 1ms
memory: 3968kb
input:
9 4 0.062298941747 0.379982766518 0.000000000000 0.335827002916 0.238024873877 0.000000000000 0.368555159260 0.154177511533 4 0.271980593498 0.402027829795 0.000000000000 0.242759569523 0.006597351582 0.000000000000 0.412952594723 0.011043306806 4 0.713919783914 0.000000000000 0.775523766209 0.02973...
output:
0.99999999996639450162 0.92363973808180098451 0.99999999996372403198 1.00000000000000000000 0.58837442195074036831 0.99999999999743319771 0.63868110357889759741 0.80435210645161007645 0.39466992927456314585 0.72379303421839173049 0.24284919938718618383 0.99999999999993987438 0.00000000000000000000 ...
result:
ok OK
Test #20:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
12 4 0.011736358846 0.082356480218 0.408765987214 0.000000000000 0.506829492828 0.122146405389 0.000000000000 0.183574392246 3 0.518781549596 0.245694689851 0.000000000000 0.398529593227 0.074761480444 0.000000000000 4 0.075538054618 0.530132543078 0.000000000000 0.488866489116 0.155089097424 0.0109...
output:
0.63884202608730757833 0.65698148644873488947 1.00000000000000000000 0.84131822591086309745 0.99999999999937204349 0.99795856389197660759 0.56632343045417897097 0.72856263705209691953 1.00000000000000000000 0.30049218743617844794 1.00000000000000000000 0.84131822591086309745 0.63884202608730757833 ...
result:
ok OK
Test #21:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
14 4 0.238874723659 0.350932855333 0.056257209931 0.347991971885 0.000000000000 0.014112992049 0.083758710992 0.000000000000 3 0.000000000000 0.000000000000 0.074629721440 0.057264984008 0.050867075265 0.098486920063 5 0.000000000000 0.100859535910 0.152266736787 0.000000000000 0.585330206242 0.2675...
output:
0.62817205871839969244 0.17959046741917860423 0.66141463876121626769 0.00000000000000000000 1.00000000000000000000 0.00000000000000000000 1.00000000000000000000 0.08493937962827451636 0.09325547064473611184 0.49058872653124181793 0.00000000000009181828 0.47824810618260482910 0.00000000000000000000 ...
result:
ok OK
Test #22:
score: 0
Accepted
time: 1ms
memory: 4096kb
input:
25 4 0.000000000000 0.627504305794 0.147063422648 0.000000000000 0.282537740951 0.083274926848 0.087264778840 0.609639797093 3 0.040754587534 0.053855777929 0.019823186956 0.059913069526 0.000000000000 0.000000000000 4 0.000000000000 0.138379187270 0.054487787984 0.000000000000 0.282847594751 0.1139...
output:
0.62039659294378536603 0.00000000000037386367 0.35047097646907691482 0.58526016919143030728 0.23445056080921897442 0.47650692780844237321 0.53132200455226269941 0.00000000000000000003 0.13061739870280181601 0.64316903735706274241 0.14213980200294540117 0.62467448318976533101 0.19692636513244654601 ...
result:
ok OK
Test #23:
score: -100
Runtime Error
input:
31 4 0.335089288956 0.202130218860 0.111257412594 0.213056135994 0.000000000000 0.115005293141 0.101353839372 0.000000000000 5 0.368599476325 0.185829203903 0.028334455772 0.164205533565 0.000000000000 0.125424247883 0.009151606319 0.000000000000 0.420642774919 0.030024538656 4 0.014611117134 0.4683...