QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#870121 | #8620. Jigsaw Puzzle | ucup-team5008# | WA | 1ms | 4096kb | C++20 | 2.5kb | 2025-01-25 14:54:44 | 2025-01-25 14:54:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep2(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define rep(i,j) rep2(i,0,j)
#define rrep2(i,j,k) for(ll i=ll(j)-1;i>=ll(k);i--)
#define rrep(i,j) rrep2(i,j,0)
#define SZ(a) ll(a.size())
#define all(a) a.begin(),a.end()
#define eb emplace_back
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vl>;
const ll inf=LLONG_MAX/4;
template<typename T>
bool chmin(T& a,T b){return a>b?a=b,1:0;}
template<typename T>
bool chmax(T& a,T b){return a<b?a=b,1:0;}
using ld=long double;
using Pt=complex<ld>;
using vt=vector<Pt>;
const ld EPS=1e-12;
using P=pair<ll,ll>;
using vp=vector<P>;
using vvp=vector<vp>;
using F=pair<ld,ld>;
#define ln "\n"
#define r(a) real(a)
#define i(a) imag(a)
bool equal(ld a,ld b){return abs(a-b)<=EPS;}
bool equal(Pt a,Pt b){return equal(r(a),r(b)) && equal(i(a),i(b));}
ld cross(Pt a,Pt b){return r(a)*i(b)-i(a)*r(b);}
ld dot(Pt a,Pt b){return r(a)*r(b)+i(a)*i(b);}
ld cross(Pt a,Pt b,Pt c){return cross(b-a,c-a);}
Pt input(){
ld x,y;cin>>x>>y;
return Pt(x,y);
}
Pt tr(Pt p0,Pt p1,Pt q0,Pt q1,Pt r){
Pt dp=p1-p0,dq=q1-q0;
Pt num(cross(dp,dq),dot(dp,dq));
return q0+Pt(cross(r-p0,num),dot(r-p0,num))/norm(dp);
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cout<<fixed<<setprecision(15);
ll n;cin>>n;
vl m(n);
vector<vt> p(n);
rep(i,n){
cin>>m[i];
p[i].resize(m[i]);
rep(j,m[i]) p[i][j]=input();
}
vector<bool> flag(n);
vector<vt> ans(n);
queue<ll> que;
auto comp=[&](ld a,ld b){
return a+EPS<b;
};
map<ld,vp,decltype(comp)> data{comp};
rep(i,n){
ans[i].resize(m[i]);
rep(j,m[i]){
Pt a=p[i][(j+m[i]-1)%m[i]];
Pt b=p[i][j], c=p[i][(j+1)%m[i]];
if(equal(dot(b-a,b-c),0)) continue;
data[abs(b-c)].eb(i,j);
}
}
rep(i,n){
rep(j,m[i]){
Pt a=p[i][(j+m[i]-1)%m[i]],
b=p[i][j],
c=p[i][(j+1)%m[i]];
if(equal(dot(b-a,b-c),0)){
ll nxt=i;
rep(k,m[nxt]){
ans[nxt][k]=tr(b,c,Pt(0,0),Pt(1,0)*abs(b-c),p[nxt][k]);
}
flag[i]=true;
que.push(i);
goto XYZ;
}
}
}
XYZ:
while(!que.empty()){
ll now=que.front(); que.pop();
rep(j,m[now]){
Pt b=p[now][j], c=p[now][(j+1)%m[now]];
if(!data.count(abs(b-c))) continue;
for(auto el:data[abs(b-c)]){
if(el==make_pair(now,j)) continue;
ll nxt=el.first;
if(flag[nxt]) continue;
flag[nxt]=true;
rep(k,m[nxt]){
ans[nxt][k]=tr(p[nxt][el.second],p[nxt][(el.second+1)%m[nxt]],ans[now][(j+1)%m[now]],ans[now][j],p[nxt][k]);
}
que.push(nxt);
}
}
}
rep(i,n){
rep(j,m[i]) cout<<r(ans[i][j])<<" "<<i(ans[i][j])<<ln;
cout<<ln;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
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.277161636324044 0.000000000000000 0.473262431361152 0.793116644514534 0.000000000002824 0.728029248282284 0.000000000000000 0.000000000000000 0.524415046517553 0.999999999997775 0.000000000003896 1.000000000000263 0.000000000002824 0.728029248282284 0.473262431361152 0.793116644514534 1.00000000...
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.000000000000000 0.000000000000000 0.999999999999604 0.000000000000000 0.999999999999946 0.942351325518608 0.000000000000243 0.915617694160293 0.000000000000243 0.915617694160293 0.999999999999946 0.942351325518608 0.999999999999940 0.999999999999970 0.000000000000177 0.999999999999978
result:
ok OK
Test #3:
score: 0
Accepted
time: 0ms
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.000000000000000 0.000000000000000 0.272945983582046 -0.000000000000000 0.597394024845134 1.000000000000214 0.000000000000399 1.000000000000532 0.597394024845134 1.000000000000214 0.272945983582046 0.000000000000000 1.000000000000839 0.000000000000319 1.000000000000508 1.000000000000731
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.000000000000000 0.000000000000000 1.000000000000362 0.000000000000000 1.000000000000178 0.353234188074805 0.000000000000080 0.915770346811862 0.000000000000080 0.915770346811862 1.000000000000178 0.353234188074805 1.000000000000836 0.999999999999246 0.000000000000185 0.999999999999914
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.000000000000092 0.985962865025225 -0.000000000000011 0.664314798085983 0.000000000000000 0.000000000000000 1.000000000000470 -0.000000000000000 -0.000000000000011 0.664314798085983 1.000000000000092 0.985962865025225 1.000000000000448 1.000000000000535 0.000000000000174 0.999999999999688
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.999999999999551 0.083254070032369 -0.000000000000841 0.069952114863932 0.000000000000000 0.000000000000000 0.999999999999521 0.000000000000000 -0.000000000000841 0.069952114863932 0.999999999999551 0.083254070032369 0.999999999999812 1.000000000000789 -0.000000000000307 1.000000000000756
result:
ok OK
Test #7:
score: 0
Accepted
time: 1ms
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.000000000000000 0.000000000000000 0.970506356543503 0.000000000000000 0.327340655552202 1.000000000000178 0.000000000000731 0.999999999999717 0.970506356543503 -0.000000000000000 1.000000000000174 0.000000000000488 1.000000000000421 0.999999999999694 0.327340655552202 1.000000000000178
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.999999999999740 0.788125876212100 -0.000000000000268 0.101166862931752 0.000000000000000 0.000000000000000 0.999999999999714 -0.000000000000000 0.999999999999457 0.806384053343768 0.999999999999692 1.000000000001009 -0.000000000000547 1.000000000001008 -0.000000000000728 0.982643180339327 0.9999...
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.000000000000408 0.322871902467164 0.000000000000000 0.000000000000000 1.000000000000575 0.000000000000000 1.000000000000373 0.255897520583282 0.100575406162766 0.390517770007990 0.000000000001178 1.000000000000008 0.000000000000451 0.405571267940372 0.100575406162766 0.390517770007990 1.000000000...
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.538791330606540 0.494251903795092 -0.000000000000095 0.512182010181747 0.000000000000000 0.000000000000000 0.929095371702259 0.000000000000000 0.999999999999942 0.478903623228790 0.999999999999883 1.000000000000252 0.139408901909673 1.000000000001081 0.538791330606540 0.494251903795092 0.9290953...
result:
ok OK
Test #11:
score: -100
Wrong Answer
time: 0ms
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.000000000000423 0.559656675047217 0.000000000000000 0.000000000000000 0.988991383211044 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.0000000...
result:
wrong answer Figures 0 and 1 intersect. Area: 0.2767478