QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#870593#8620. Jigsaw Puzzleucup-team159#RE 1ms4096kbC++204.8kb2025-01-25 16:58:322025-01-25 16:58:36

Judging History

你现在查看的是最新测评结果

  • [2025-01-25 16:58:36]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:4096kb
  • [2025-01-25 16:58:32]
  • 提交

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...

output:


result: