提出 #64985060

---

ソースコード 拡げる

    #include <bits/stdc++.h>
 //  #include <atcoder/all>
  //  using namespace atcoder;
     
     
    // tabaicho see https://boostjp.github.io/tips/multiprec-int.html   
    // #include <boost/multiprecision/cpp_int.hpp>
     
    // using namespace boost::multiprecision;
     
    // cpp_int
    // int128_t
    // int256_t
    // int512_t
    // int1024_t
     
    // uint128_t
    // uint256_t
    // uint512_t
    // uint1024_t
     

     
  #define int long long
     #define inf  1000000007
    // #define inf  998244353
     
     #define pa pair<int,int>
     #define ppa pair<pa,pa>
     #define ll long long
     #define PI 3.14159265358979323846
     #define  mp make_pair
     #define  pb push_back
     #define EPS (1e-8)
     
          using namespace std;
                                              
     int dx[8]={1,0,-1,0,1,1,-1,-1};
     int dy[8]={0,-1,0,1,-1,1,1,-1};
                                                
    class pa3{
    	public:
    	int x;
    	int y,z;
    	pa3(int x=0,int y=0,int z=0):x(x),y(y),z(z) {}
    	bool operator < (const pa3 &p) const{
    		if(x!=p.x) return x<p.x;
    		if(y!=p.y) return y<p.y;
    		 return z<p.z;
    		//return x != p.x ? x<p.x: y<p.y;
    	}
    	bool operator > (const pa3 &p) const{
    		if(x!=p.x) return x>p.x;
    		if(y!=p.y) return y>p.y;
    		 return z>p.z;
    		//return x != p.x ? x<p.x: y<p.y;
    	}
    	bool operator == (const pa3 &p) const{
    		return x==p.x && y==p.y && z==p.z;
    	}
    		bool operator != (const pa3 &p) const{
    			return !( x==p.x && y==p.y && z==p.z);
    	}
    	pa3 operator + (pa3 p) {return pa3(x+p.x,y+p.y,z+p.z);}
    	pa3 operator - (pa3 p) {return pa3(x-p.x,y-p.y,z-p.z);}
     
    };
     
    class pa4{
    	public:
    	int x;
    	int y,z,w;
    	pa4(int x=0,int y=0,int z=0,int w=0):x(x),y(y),z(z),w(w) {}
    	bool operator < (const pa4 &p) const{
    		if(x!=p.x) return x<p.x;
    		if(y!=p.y) return y<p.y;
    		if(z!=p.z)return z<p.z;
    		return w<p.w;
    		//return x != p.x ? x<p.x: y<p.y;
    	}
    	bool operator > (const pa4 &p) const{
    		if(x!=p.x) return x>p.x;
    		if(y!=p.y) return y>p.y;
    		if(z!=p.z)return z>p.z;
    		return w>p.w;
    		//return x != p.x ? x<p.x: y<p.y;
    	}
    	bool operator == (const pa4 &p) const{
    		return x==p.x && y==p.y && z==p.z &&w==p.w;
    	}
    		
     
    };
    class pa2{
    	public:
    	int x,y;
    	pa2(int x=0,int y=0):x(x),y(y) {}
    	pa2 operator + (pa2 p) {return pa2(x+p.x,y+p.y);}
    	pa2 operator - (pa2 p) {return pa2(x-p.x,y-p.y);}
    	bool operator < (const pa2 &p) const{
    		return x != p.x ? x<p.x: y<p.y;
    	}
    	bool operator > (const pa2 &p) const{
    		return x != p.x ? x>p.x: y>p.y;
    	}
    	bool operator == (const pa2 &p) const{
    		return abs(x-p.x)==0 && abs(y-p.y)==0;
    	}
    	bool operator != (const pa2 &p) const{
    		return !(abs(x-p.x)==0 && abs(y-p.y)==0);
    	}
    		
     
    };
     
     
     
    string itos( int i ) {
    	ostringstream s ;
    	s << i ;
    	return s.str() ;
    }
     
    int Gcd(int v,int b){
    	if(v==0) return b;
    	if(b==0) return v;
    	if(v>b) return Gcd(b,v);
    	if(v==b) return b;
    	if(b%v==0) return v;
    	return Gcd(v,b%v);
    }
     
     
     
    int extgcd(int a, int b, int &x, int &y) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        int d = extgcd(b, a%b, y, x);
        y -= a/b * x;
        return d;
    }
    pa operator+(const pa & l,const pa & r) {   
        return {l.first+r.first,l.second+r.second};                                    
    }    
    pa operator-(const pa & l,const pa & r) {   
        return {l.first-r.first,l.second-r.second};                                    
    }  
     
     
    pair<double,double> operator-(const pair<double,double> & l,const pair<double,double> & r) {   
        return {l.first-r.first,l.second-r.second};                                    
    }  
     
    ostream& operator<<(ostream& os, const vector<int>& VEC){
    	for(auto v:VEC)os<<v<<" ";
        return os;
    }
     
     ostream& operator<<(ostream& os, const pair<double,double>& PAI){
    	os<<PAI.first<<" : "<<PAI.second;
        return os;
    }
     
     
    ostream& operator<<(ostream& os, const pa& PAI){
    	os<<PAI.first<<" : "<<PAI.second;
        return os;
    }

    ostream& operator<<(ostream& os, const pa2& PAI){
    	os<<PAI.x<<", "<<PAI.y;
        return os;
    }
       
    ostream& operator<<(ostream& os, const pa3& PAI){
    	os<<PAI.x<<" : "<<PAI.y<<" : "<<PAI.z;
        return os;
    }
     
    ostream& operator<<(ostream& os, const pa4& PAI){
    	os<<PAI.x<<" : "<<PAI.y<<" : "<<PAI.z<<" : "<<PAI.w;
        return os;
    }
     
    ostream& operator<<(ostream& os, const vector<pa2>& VEC){
    	for(auto v:VEC)os<<v<<" ";
        return os;
    }
     
     
    ostream& operator<<(ostream& os, const vector<pa3>& VEC){
    	for(auto v:VEC){
    		os<<v<<" ";
    	os<<endl;
    	}
        return os;
    }
     
    int beki(int wa,ll rr,int warukazu){
    	if(rr==0) return 1%warukazu;
    	if(rr==1) return wa%warukazu;
    	wa%=warukazu;
    	if(rr%2==1) return ((ll)beki(wa,rr-1,warukazu)*(ll)wa)%warukazu;
    	ll zx=beki(wa,rr/2,warukazu);
    	return (zx*zx)%warukazu;
    }
     
     
                  
    int pr[3000302];
    int inv[3000302];
     
     
     
     
   const int mod=998244353;
//   const int mod=1000000007;
	const int inff=(1ll<<62)-1+(1ll<<62);
    int comb(int nn,int rr){
    	//if(nn==-1&&rr==-1)return 1;
    	if(rr<0 || rr>nn || nn<0) return 0;
    	int r=pr[nn]*inv[rr];
    	r%=mod;
    	r*=inv[nn-rr];
    	r%=mod;
    	return r;
    }
     
    void gya(int ert){
    	pr[0]=1;
    	for(int i=1;i<=ert;i++){
    		pr[i]=((ll)pr[i-1]*i)%mod;
    	}
    		inv[ert]=beki(pr[ert],mod-2,mod);
    	for(int i=ert-1;i>=0;i--){
    		inv[i]=(ll)inv[i+1]*(i+1)%mod;
    	}
    }
     
     
    int beki(int a,int b){
    	int ANS=1;
    	int be=a%mod;
    	while(b){
    		if(b&1){
    			ANS*=be;
    			ANS%=mod;
    		}
    		be*=be;
    		be%=mod;
    		b/=2;
    	}
    	return ANS;
    }
     
vector<int>zaatu(vector<int>vec){
	sort(vec.begin(),vec.end());
	vec.erase(unique(vec.begin(),vec.end()),vec.end());
	return vec;
}

     
struct unionfind{
	private:
	public:
	
	vector<int> par,ranks,kosuu;
	
	void shoki(int N){
		par.resize(N+1,0);
		ranks.resize(N+1,0);
		kosuu.resize(N+1,1);
		for(int i=0;i<=N;i++){
			par[i]=i;
		}
	}
	
	int root(int x){
		return par[x]==x ? x : par[x]=root(par[x]);
	}
	
	bool same(int x,int y){
		return root(x)==root(y);
	}
	bool is_root(int x){
		return x==root(x);
	}
	void unite(int x,int y){
		x=root(x);
		y=root(y);
		int xx=kosuu[x],yy=kosuu[y];
		if(x==y) return;
		if(ranks[x]<ranks[y]){
			par[x]=y;
			kosuu[y]=yy+xx;
		}
		else {
			par[y]=x;
			if(ranks[x]==ranks[y]) ranks[x]=ranks[x]+1;
			kosuu[x]=yy+xx;
		}
		return;
	}
};



                    
                  //   cin.tie(0);
        		//	ios::sync_with_stdio(false);
        			//priority_queue<pa3,vector<pa3>,greater<pa3>> pq;            
                     //sort(ve.begin(),ve.end(),greater<int>());
    //    mt19937(clock_per_sec);
      //  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) ;
     // a,b,c : positive int   a*b<=c  <=>  a<=c/b
     // a,b,c : positive int   a*b>c  <=>  a>c/b


struct convex_hull_integer{
	
	vector<pa2>points,upper,lower;
	
	
	int cross(pa2 a,pa2 b){
		return a.x*b.y-a.y*b.x;
	}
	
	
	// include point on edge
	//
	//   upper: ue and hidari
	//   ________
	//  /         /
	// /  _______/
	//   lower: sita and migi
	
	void shoki(vector<pa2>in){
		
		sort(in.begin(),in.end());
		//cout<<in<<endl;
		int ls=0,us=0;
		for(auto v:in){
			while(1){
				if(ls<=1){
					lower.pb(v);
					ls++;
					break;
				}
				else{
					if(cross(lower[ls-1]-lower[ls-2],v-lower[ls-2])<0){
						lower.pop_back();
						ls--;
						continue;
					}
					else{
						lower.pb(v);
						ls++;
						break;
					}
				}
			}
		}
		
		reverse(in.begin(),in.end());
		for(auto v:in){
			while(1){
				if(us<=1){
					upper.pb(v);
					us++;
					break;
				}
				else{
					if(cross(upper[us-1]-upper[us-2],v-upper[us-2])<0){
						upper.pop_back();
						us--;
						continue;
					}
					else{
						upper.pb(v);
						us++;
						break;
					}
				}
			}
		}
		
		reverse(upper.begin(),upper.end());
	}
	
	int get(pa2 v,int a,int b){
		return v.x*a+v.y*b;
	}
	
	int max_val(int a,int b){
		// return max(a*x+b*y) where (x,y) is in this class
		if(a==0&&b==0)return 0;
		if(b==0){
			if(a>0)return lower.back().x*a;
			else return lower[0].x*a;
		}
		else if(b>0){
			int s=upper.size();
			if(s==1){
				return a*upper[0].x+b*upper[0].y;
			}
			if(get(upper[0],a,b)>=get(upper[1],a,b))return get(upper[0],a,b);
			if(get(upper[s-2],a,b)<get(upper[s-1],a,b))return get(upper[s-1],a,b);
			
			int l=1,r=s-2;
			while(1){
				int m=(l+r)/2;
				int p1=get(upper[m-1],a,b);
				int p2=get(upper[m],a,b);
				if(p1>=p2){
					r=m-1;
					continue;
				}
				int p3=get(upper[m+1],a,b);
				if(p2<p3){
					l=m+1;
					continue;
				}
				return p2;
			}
		}
		else{
			int s=lower.size();
			if(s==1){
				return a*lower[0].x+b*lower[0].y;
			}
			if(get(lower[0],a,b)>=get(lower[1],a,b))return get(lower[0],a,b);
			if(get(lower[s-2],a,b)<get(lower[s-1],a,b))return get(lower[s-1],a,b);
			
			int l=1,r=s-2;
			while(1){
				int m=(l+r)/2;
				int p1=get(lower[m-1],a,b);
				int p2=get(lower[m],a,b);
				if(p1>=p2){
					r=m-1;
					continue;
				}
				int p3=get(lower[m+1],a,b);
				if(p2<p3){
					l=m+1;
					continue;
				}
				return p2;
			}			
		}
	}
	
};


const int R=1000000;
using T=array<int,8>;


double dis(int a,int b,int c,int d){
	double p=c-a+0.0;
	double q=d-b+0.0;
	return sqrt(p*p+q*q);
}

double get_score(vector<T>ans){
	double score=0;
	int n=ans.size();
	for(int i=1;i<n;i++){
		score+=max(dis(ans[i][0],ans[i][1],ans[i-1][0],ans[i-1][1])+dis(ans[i][2],ans[i][3],ans[i-1][2],ans[i-1][3]),
			dis(ans[i][4],ans[i][5],ans[i-1][4],ans[i-1][5])+dis(ans[i][6],ans[i][7],ans[i-1][6],ans[i-1][7]));
	}
	return score;
}
int C,D;
bool hi4(pa4 a,pa4 b){
	return (a.x-C)*(D-b.y)<(b.x-C)*(D-a.y);
}
bool hi(pa3 a,pa3 b){
	return (a.x-C)*(D-b.y)<(b.x-C)*(D-a.y);
}
vector<T> solution_round(vector<pa3> V,int dir,int ty,int sw){
	//dir=0;
	if(sw){
		for(auto &v:V)swap(v.x,v.y);
	}
	
	for(int i=0;i<dir;i++){
		for(auto &v:V){
			int u1=v.y;
			int u2=R-v.x;
			v.x=u1,v.y=u2;
		}
	}
	
	int ymin=inf,xmax=-inf,xmin=inf,ymax=-inf;
	for(auto v:V){
		ymin=min(ymin,v.y);
		xmax=max(xmax,v.x);
		xmin=min(xmin,v.x);
		ymax=max(ymax,v.y);
	}
	
	
	if(ty==0){
		C=0,D=R;
	}
	else if(ty==1){
		C=xmin-1,D=ymax+1;
	}
	else{
		C=rand()%xmin;
		D=R-rand()%(R-ymax);
	}
	
	vector<pa2>in;
	for(auto v:V)in.pb(pa2(v.x,v.y));
	in.pb(pa2(0,ymin));
	in.pb(pa2(xmax,R));
	 convex_hull_integer ss;
	
	ss.shoki(in);
	//cout<<ss.lower<<endl;
	
	vector<pa2>kouho;
	pa2 lasp=pa2(C,ymin);
	kouho.pb(pa2(C,ymin));
	for(auto v:ss.lower){
		if(v==pa2(C,ymin))continue;
		int f1=v.x-lasp.x;
		int f2=v.y-lasp.y;
		//int f=Gcd(f1,f2);
		
		int pos=0;
		for(int j=1;j<=f1;j++){
			while(1){
				if(f2*j/f1>=pos){
					kouho.pb(pa2(lasp.x+j,lasp.y+pos));
					pos++;
				}
				else{
					pos--;
					break;
				}
			}
		}
		lasp=v;
		
	}
	while(kouho.back().y!=D){
		kouho.pb(kouho.back());
		kouho.back().y++;
	}
	/*
	for(int i=0;i<(int)kouho.size()-2;i++){
		if(kouho[i].x*(R-kouho[i+1].y)>=kouho[i+1].x*(R-kouho[i].y)){
			cout<<kouho[i]<<" "<<kouho[i+1]<<endl;
		}
		assert(kouho[i].x*(R-kouho[i+1].y)<kouho[i+1].x*(R-kouho[i].y));
	}
	*/
	
	set<int>se[2];
	for(auto v:V){
		int si=0,ue=(int)kouho.size();
		while(ue-si>1){
			int me=(ue+si)/2;
			if((kouho[me].x-C)*(D-v.y)<(v.x-C)*(D-kouho[me].y)){
				si=me;
			}
			else ue=me;
		}
		se[v.z].insert(ue);
		//cout<<v<<" "<<ue<<endl;
	}
	
	for(auto v:se[0])if(se[1].count(v)){

		return vector<T>();
	}
	
	vector<pa3>tmp;
	for(auto v:se[0])tmp.pb(pa3(kouho[v].x,kouho[v].y,0));
	for(auto v:se[1])tmp.pb(pa3(kouho[v].x,kouho[v].y,1));
	map<pa2,int> tmpma;
	for(auto v:tmp)tmpma[pa2(v.x,v.y)]=v.z;
	sort(tmp.begin(),tmp.end(),hi);

	sort(V.begin(),V.end());
	vector<pa4>kukan;
	for(auto v:tmp){
		if(kukan.size()==0 || kukan.back().z!=v.z)kukan.pb(pa4(v.x,v.y,v.z,0));
		else kukan.back().x=v.x,kukan.back().y=v.y;
	}
	for(auto v:ss.lower)if(v!=pa2(C,ymin)&&v!=pa2(xmax,D)){
		int it=-1;
		for(int i=0;i<kukan.size();i++)if(kukan[i].x==v.x&&kukan[i].y==v.y){
			it=i;
			break;
		}
		if(it==-1)kukan.pb(pa4(v.x,v.y,tmpma[pa2(v.x,v.y)],1));
		else kukan[it].w=1;
	}
	sort(kukan.begin(),kukan.end(),hi4);
	//for(auto v:kukan)cout<<v.x<<" "<<v.y<<" "<<v.z<<" "<<v.w<<endl;
	vector<T>ans;
	pa2 a,b;
	int id=min(*se[0].begin(),*se[1].begin())-1;
	a=pa2(kouho[id].x,kouho[id].y);
	b=a;
	
	int it=0;
	ans.pb({a.x,a.y,0,R,b.x,b.y,0,R});
	
	
	int n=kukan.size();
	while(it<n){
		if(kukan[it].z==0){
			if(it<n-1&&kukan[it].w==0&&kukan[it+1].z==1){
				a.x=kukan[it].x;
				a.y=kukan[it].y;
				b.x=kukan[it+1].x;
				b.y=kukan[it+1].y;
				ans.pb({a.x,a.y,0,R,b.x,b.y,0,R});
				it+=2;
			}
			else if(it<n-1&&kukan[it].w==0&&kukan[it+1].z==0){
				a.x=kukan[it+1].x;
				a.y=kukan[it+1].y;
				b.x=kukan[it+1].x;
				b.y=kukan[it+1].y;
				ans.pb({a.x,a.y,0,R,b.x,b.y,0,R});
				it+=2;
			}
			else if(it==n-1){
				a.x=kukan[it].x;
				a.y=kukan[it].y;
				ans.pb({a.x,a.y,0,R,b.x,b.y,0,R});
				it++;
			}
			else{
				a.x=kukan[it].x;
				a.y=kukan[it].y;
				b.x=kukan[it].x;
				b.y=kukan[it].y;
				ans.pb({a.x,a.y,0,R,b.x,b.y,0,R});
				it++;
			}
			
		}
		else{
			if(it<n-1&&kukan[it].w==0&&kukan[it+1].z==1){
				b.x=kukan[it+1].x;
				b.y=kukan[it+1].y;
				ans.pb({a.x,a.y,0,R,b.x,b.y,0,R});
				it+=2;
			}
			else{
				b.x=kukan[it].x;
				b.y=kukan[it].y;
				ans.pb({a.x,a.y,0,R,b.x,b.y,0,R});
				it++;
			}
		}
	}
	//cout<<ans<<endl;
	//for(auto v:ans)cout<<v[0]<<" "<<v[1]<<" "<<v[2]<<" "<<v[3]<<" "<<v[4]<<" "<<v[5]<<" "<<v[6]<<" "<<v[7]<<"\n";
	//exit(1);
	for(int i=0;i<4-dir;i++){
		for(int k=0;k<4;k++){
			for(auto &v:ans){
				int u1=v[2*k+1];
				int u2=R-v[2*k];
				v[2*k]=u1,v[2*k+1]=u2;
			}
		}
	}
	
	if(sw){
		for(int k=0;k<4;k++){
			for(auto &v:ans){
				swap(v[2*k],v[2*k+1]);
			}
		}
	}
	return ans;
}


vector<T> solution(vector<pa3> V,int dir){
	//dir=0;
	for(int i=0;i<dir;i++){
		for(auto &v:V){
			int u1=v.y;
			int u2=R-v.x;
			v.x=u1,v.y=u2;
		}
	}
	
	
	sort(V.begin(),V.end());
	for(int i=1;i<(int)V.size();i++)if(V[i].x==V[i-1].x){
		if(V[i].z!=V[i-1].z)return vector<T>();
	}
	vector<pa3>kukan;
	for(auto v:V){
		if(kukan.size()==0 || kukan.back().z!=v.z)kukan.pb(pa3(v.x,v.x,v.z));
		else kukan.back().y=v.x;
	}
	vector<T>ans;
	
	int a,b;
	a=kukan[0].x-1;
	b=a;
	
	int it=0;
	ans.pb({a,0,a,R,b,0,b,R});
	
	
	int n=kukan.size();
	while(it<n){
		if(kukan[it].z==0){
			if(it==n-1){
				a=kukan[it].y;
				ans.pb({a,0,a,R,b,0,b,R});
				it++;
			}
			else{
				a=kukan[it].y;
				b=kukan[it+1].y;
				ans.pb({a,0,a,R,b,0,b,R});
				it+=2;
			}
		}
		else{
			if(it==n-1){
				b=kukan[it].y;
				ans.pb({a,0,a,R,b,0,b,R});
				it++;
			}
			else{
				b=kukan[it].y;
				//a=kukan[it+1].y;
				ans.pb({a,0,a,R,b,0,b,R});
				it++;
			}
		}
	}
	
	
	for(int i=0;i<4-dir;i++){
		for(int k=0;k<4;k++){
			for(auto &v:ans){
				int u1=v[2*k+1];
				int u2=R-v[2*k];
				v[2*k]=u1,v[2*k+1]=u2;
			}
		}
	}
	
	
	return ans;
}


void solve(){
	int X,Y,Z;
	
	cin>>X>>Y>>Z;
	
	assert(Z==0);
	
	vector<pa3>V;
	for(int i=0;i<X;i++){
		int x,y;
		cin>>x>>y;
		V.pb(pa3(x,y,0));
	}
	for(int i=0;i<Y;i++){
		int x,y;
		cin>>x>>y;
		V.pb(pa3(x,y,1));
	}
	double sol=1e50;
	vector<T> ans;
	for(int d=0;d<4;d++){
		vector<T> x=solution(V,d);
		if(x.size()==0)continue;
		double score = get_score(x);
	//	cout<<score<<endl;
		if(sol>score) ans=x,sol=score;
	}

	for(int d=0;d<4;d++){
			for(int c=0;c<4;c++){for(int sw=0;sw<2;sw++){
		vector<T> x=solution_round(V,d,c,sw);
		if(x.size()==0)continue;
		double score = get_score(x);
	//	cout<<score<<endl;
		if(sol>score) ans=x,sol=score;
			}
	}
	}
	
	for(auto v:ans){
		cout<<v[0]<<" "<<v[1]<<" "<<v[2]<<" "<<v[3]<<" "<<v[4]<<" "<<v[5]<<" "<<v[6]<<" "<<v[7]<<"\n";
	}
	
	//cout<<sol<<endl;
}

    
    signed main(){
    	//mod=inf;
    	//mae();
   	cin.tie(0);
    	ios::sync_with_stdio(false);
    	int n=1;
    //cin>>n;
    	for(int i=0;i<n;i++){
    		solve();
    	}
    	return 0;
    	
    }

提出情報

コンパイルエラー

Main.cpp: In function ‘std::vector<std::array<long long int, 8> > solution_round(std::vector<pa3>, long long int, long long int, long long int)’:
Main.cpp:600:30: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<pa4>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  600 |                 for(int i=0;i<kukan.size();i++)if(kukan[i].x==v.x&&kukan[i].y==v.y){
      |                             ~^~~~~~~~~~~~~

ジャッジ結果