QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#870114#8620. Jigsaw Puzzleucup-team5008#WA 1ms4096kbC++202.5kb2025-01-25 14:53:262025-01-25 14:53:26

Judging History

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

  • [2025-01-25 14:53:26]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4096kb
  • [2025-01-25 14:53:26]
  • 提交

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[norm(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(norm(b-c))) continue;
			for(auto el:data[norm(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: -100
Wrong Answer
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.000000000000000 0.000000000000000
0.000000000000000 0.000000000000000
0.000000000000000 0.000000000000000
0.000000000000000 0.000000000000000


result:

wrong answer Figures 0 and 1 intersect. Area: 0.4351700