QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#870245 | #8620. Jigsaw Puzzle | ucup-team159# | WA | 1ms | 4224kb | C++20 | 5.6kb | 2025-01-25 15:30:59 | 2025-01-25 15:31:02 |
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 = double;
using P = complex<D>;
using L = pair<P,P>;
using Pol = vector<P>;
struct C{P p;D r;};
D inf=1e50,eps=1e-10,pi=acos(0.0)*2;
bool eq(D a, D b) { return abs(a-b)<eps;}
bool eq(P a, P b) { return abs(a-b)<eps;}
int sig(D a) { return eq(a,0) ? 0 : (a>0 ? 1 : -1);}
int large(D a,D b){return eq(a,b)?0:(a>b?1:-1);}
bool compxy (const P& l, const P& r){
return eq(l.real(),r.real()) ? l.imag()<r.imag() : l.real() < r.real();
}
bool compyx (const P& l, const P& r){
return eq(l.imag(),r.imag()) ? l.real()<r.real() : l.imag() < r.imag();
}
inline D dot(P a, P b) { return real(conj(a)*b);}
inline D cro(P a, P b) { return imag(conj(a)*b);}
//enum ENCCW{CCW(left)=1, CW(right)=-1, FRONT=-2, BACK=2, ON=0};
//ON優先(including endpoint)
inline int ccw (P a, P b, P c){
if(sig(cro(b-a,c-a))==1) return 1;
if(sig(cro(b-a,c-a))==-1) return -1;
b -= a, c -= a;
if(!sig(abs(c)) || !sig(abs(c-b))) return 0;
if(dot(b,c) < 0) return 2;
if(dot(-b, c-b) < 0) return -2;
return 0;
}
inline int ccw(L a,P p){return ccw(a.fs,a.sc,p);}
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<pair<P,P>> 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]-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});
}
};
{
D cho = 0;
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] = 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 = 0;
int ii = -1, jj = -1;
rep(i,N) if(!used[i]){
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;
}
}
}
if(ii != -1){
assert(eq(best,len));
Put(ii,jj,a,b);
}
}
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: 4224kb
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.72283836367552312119 0.79311664451551733279 0.52673756864208631789 0.72802924828096515775 1.00000000000000000000 0.00000000000000000000 0.99999999999973510079 0.99999999999912803084 0.47558495348664409086 0.99999999999910982318 1.00000000000000000000 0.72802924828096515775 ...
result:
ok OK
Test #2:
score: 0
Accepted
time: 1ms
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.99999999999986233234 0.99999999999990907273 0.00000000000032720701 0.99999999999990063504 0.00000000000000000000 0.05764867448135791578 0.99999999999962674302 0.08438230583967944176 0.99999999999962685404 0.08438230583967948339 0.00000000000000000000 0.05764867448135792272 0.00000000000000000000 ...
result:
ok OK
Test #3:
score: 0
Accepted
time: 0ms
memory: 4224kb
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.00000000000001261664 1.00000000000000000000 0.00000000000000000000 0.72705401641843225846 0.99999999999953304020 0.40260597515517443368 1.00000000000000000000 0.99999999999961319830 0.99999999999953315122 0.40260597515517443368 0.00000000000000000000 0.72705401641843225846 0.00000000000000000000 ...
result:
ok OK
Test #4:
score: 0
Accepted
time: 1ms
memory: 4224kb
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.00000000000000005551 1.00000000000000000000 0.35323418807480494452 0.00000000000008021361 0.91577034681186175735 0.00000000000008026908 0.91577034681186175735 1.00000000000000000000 0.35323418807480511106 1.00000000000000000000 ...
result:
ok OK
Test #5:
score: 0
Accepted
time: 0ms
memory: 4224kb
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.98596286502522478834 0.00000000000000000000 0.66431479808598337122 0.00000000000000000000 0.00000000000000000000 1.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.66431479808598337122 1.00000000000000000000 0.98596286502522478834 1.00000000000000000000 ...
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:
0.00000000000029126701 0.91674592996802350964 1.00000000000000000000 0.93004788513642255854 0.99999999999941269202 1.00000000000000000000 0.00000000000032363175 1.00000000000000000000 1.00000000000000000000 0.93004788513642255854 0.00000000000029126701 0.91674592996802350964 0.00000000000000000000 ...
result:
ok OK
Test #7:
score: 0
Accepted
time: 0ms
memory: 4224kb
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.99999999999985234034 1.00000000000000000000 0.02949364345620192340 0.99999999999986655119 0.67265934444832109484 0.00000000000000000000 0.99999999999984190424 0.00000000000069633188 0.02949364345620192340 0.99999999999986655119 0.00000000000000000000 0.99999999999935762496 0.00000000000000000000 ...
result:
ok OK
Test #8:
score: -100
Wrong Answer
time: 1ms
memory: 4224kb
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.00000000000000000000 1.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 -nan -nan
result:
wrong output format Expected double, but "-nan" found