QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#284657#7934. Christmas Skyucup-team087#AC ✓1573ms4308kbC++2017.1kb2023-12-16 14:17:342023-12-16 14:17:34

Judging History

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

  • [2023-12-16 14:17:34]
  • 评测
  • 测评结果:AC
  • 用时:1573ms
  • 内存:4308kb
  • [2023-12-16 14:17:34]
  • 提交

answer

#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
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 dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif

using uint=unsigned;
using ull=unsigned long long;

template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
	return os<<vc<t>(all(a));
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"{";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<"}";
}

ll read(){
	ll i;
	cin>>i;
	return i;
}

vi readvi(int n,int off=0){
	vi v(n);
	rep(i,n)v[i]=read()+off;
	return v;
}

pi readpi(int off=0){
	int a,b;cin>>a>>b;
	return pi(a+off,b+off);
}

template<class t>
void print_single(t x,int suc=1){
	cout<<x;
	if(suc==1)
		cout<<"\n";
	if(suc==2)
		cout<<" ";
}

template<class t,class u>
void print_single(const pair<t,u>&p,int suc=1){
	print_single(p.a,2);
	print_single(p.b,suc);
}

template<class T>
void print_single(const vector<T>&v,int suc=1){
	rep(i,v.size())
		print_single(v[i],i==int(v.size())-1?suc:2);
}

template<class T>
void print_offset(const vector<T>&v,ll off,int suc=1){
	rep(i,v.size())
		print_single(v[i]+off,i==int(v.size())-1?suc:2);
}

template<class T,size_t N>
void print_single(const array<T,N>&v,int suc=1){
	rep(i,N)
		print_single(v[i],i==int(N)-1?suc:2);
}

template<class T>
void print(const T&t){
	print_single(t);
}

template<class T,class ...Args>
void print(const T&t,const Args&...args){
	print_single(t,2);
	print(args...);
}

string readString(){
	string s;
	cin>>s;
	return s;
}

template<class T>
T sq(const T& t){
	return t*t;
}

void YES(bool ex=true){
	cout<<"YES\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void NO(bool ex=true){
	cout<<"NO\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void Yes(bool ex=true){
	cout<<"Yes\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void No(bool ex=true){
	cout<<"No\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
//#define CAPITAL
/*
void yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<"\n";
	#else
	cout<<"Yes"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void no(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<"\n";
	#else
	cout<<"No"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}*/
void possible(bool ex=true){
	#ifdef CAPITAL
	cout<<"POSSIBLE"<<"\n";
	#else
	cout<<"Possible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void impossible(bool ex=true){
	#ifdef CAPITAL
	cout<<"IMPOSSIBLE"<<"\n";
	#else
	cout<<"Impossible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}

constexpr ll ten(int n){
	return n==0?1:ten(n-1)*10;
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

int topbit(signed t){
	return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
	return t==0?-1:63-__builtin_clzll(t);
}
int topbit(ull t){
	return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
	return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
	return a==0?64:__builtin_ctzll(a);
}
int botbit(ull a){
	return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
	return __builtin_popcount(t);
}
int popcount(ll t){
	return __builtin_popcountll(t);
}
int popcount(ull t){
	return __builtin_popcountll(t);
}
int bitparity(ll t){
	return __builtin_parityll(t);
}
bool ispow2(int i){
	return i&&(i&-i)==i;
}
ll mask(int i){
	return (ll(1)<<i)-1;
}
ull umask(int i){
	return (ull(1)<<i)-1;
}
ll minp2(ll n){
	if(n<=1)return 1;
	else return ll(1)<<(topbit(n-1)+1);
}

bool inc(int a,int b,int c){
	return a<=b&&b<=c;
}

template<class t> void mkuni(vc<t>&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

ll rand_int(ll l, ll r) { //[l, r]
	//#ifdef LOCAL
	static mt19937_64 gen;
	/*#else
	static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
	#endif*/
	return uniform_int_distribution<ll>(l, r)(gen);
}

ll rand_int(ll k){ //[0,k)
	return rand_int(0,k-1);
}

template<class t>
void myshuffle(vc<t>&a){
	rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
}

template<class t,class u>
int lwb(const vc<t>&v,const u&a){
	return lower_bound(all(v),a)-v.bg;
}
template<class t,class u>
bool bis(const vc<t>&v,const u&a){
	return binary_search(all(v),a);
}

vvc<int> readGraph(int n,int m){
	vvc<int> g(n);
	rep(i,m){
		int a,b;
		cin>>a>>b;
		//sc.read(a,b);
		a--;b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	return g;
}

vvc<int> readTree(int n){
	return readGraph(n,n-1);
}

template<class t>
vc<t> presum(const vc<t>&a){
	vc<t> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
vc<ll> presum(const vi&a){
	vc<ll> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
//BIT で数列を管理するときに使う (CF850C)
template<class t>
vc<t> predif(vc<t> a){
	gnr(i,1,si(a))a[i]-=a[i-1];
	return a;
}
template<class t>
vvc<ll> imos(const vvc<t>&a){
	int n=si(a),m=si(a[0]);
	vvc<ll> b(n+1,vc<ll>(m+1));
	rep(i,n)rep(j,m)
		b[i+1][j+1]=b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j];
	return b;
}

//verify してないや
void transvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void transvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[j][i]=a[i][j];
	}
	a.swap(b);
	transvvc(n,m,args...);
}
//CF854E
void rotvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void rotvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[m-1-j][i]=a[i][j];
	}
	a.swap(b);
	rotvvc(n,m,args...);
}

//ソートして i 番目が idx[i]
//CF850C
template<class t>
vi sortidx(const vc<t>&a){
	int n=si(a);
	vi idx(n);iota(all(idx),0);
	sort(all(idx),[&](int i,int j){return a[i]<a[j];});
	return idx;
}
//vs[i]=a[idx[i]]
//例えば sortidx で得た idx を使えば単にソート列になって返ってくる
//CF850C
template<class t>
vc<t> a_idx(const vc<t>&a,const vi&idx){
	int n=si(a);
	assert(si(idx)==n);
	vc<t> vs(n);
	rep(i,n)vs[i]=a[idx[i]];
	return vs;
}
//CF850C
vi invperm(const vi&p){
	int n=si(p);
	vi q(n);
	rep(i,n)q[p[i]]=i;
	return q;
}

template<class t,class s=t>
s SUM(const vc<t>&a){
	return accumulate(all(a),s(0));
}

template<class t>
t MAX(const vc<t>&a){
	return *max_element(all(a));
}

template<class t>
pair<t,int> MAXi(const vc<t>&a){
	auto itr=max_element(all(a));
	return mp(*itr,itr-a.bg);
}

template<class t>
t MIN(const vc<t>&a){
	return *min_element(all(a));
}

template<class t>
pair<t,int> MINi(const vc<t>&a){
	auto itr=min_element(all(a));
	return mp(*itr,itr-a.bg);
}

vi vid(int n){
	vi res(n);iota(all(res),0);
	return res;
}

template<class S>
void soin(S&s){
	sort(all(s));
}

template<class S,class F>
void soin(S&s,F&&f){
	sort(all(s),forward<F>(f));
}

template<class S>
S soout(S s){
	soin(s);
	return s;
}

template<class S>
void rein(S&s){
	reverse(all(s));
}

template<class S>
S reout(S s){
	rein(s);
	return s;
}

template<class t,class u>
pair<t,u>&operator+=(pair<t,u>&a,pair<t,u> b){
	a.a+=b.a;a.b+=b.b;return a;}
template<class t,class u>
pair<t,u>&operator-=(pair<t,u>&a,pair<t,u> b){
	a.a-=b.a;a.b-=b.b;return a;}
template<class t,class u>
pair<t,u> operator+(pair<t,u> a,pair<t,u> b){return mp(a.a+b.a,a.b+b.b);}
template<class t,class u>
pair<t,u> operator-(pair<t,u> a,pair<t,u> b){return mp(a.a-b.a,a.b-b.b);}

template<class t>
t gpp(vc<t>&vs){
	assert(si(vs));
	t res=move(vs.back());
	vs.pop_back();
	return res;
}

template<class t,class u>
void pb(vc<t>&a,const vc<u>&b){
	a.insert(a.ed,all(b));
}

template<class t,class...Args>
vc<t> cat(vc<t> a,Args&&...b){
	(pb(a,forward<Args>(b)),...);
	return a;
}

template<class t,class u>
vc<t>& operator+=(vc<t>&a,u x){
	for(auto&v:a)v+=x;
	return a;
}

template<class t,class u>
vc<t> operator+(vc<t> a,u x){
	return a+=x;
}

template<class t,class u>
vc<t>& operator-=(vc<t>&a,u x){
	for(auto&v:a)v-=x;
	return a;
}

template<class t,class u>
vc<t>& operator-(vc<t> a,u x){
	return a-=x;
}

template<class t,class u>
void remval(vc<t>&a,const u&v){
	a.erase(remove(all(a),v),a.ed);
}

template<class t,class u>
void fila(vc<t>&vs,const u&a){
	fill(all(vs),a);
}

template<class t,class u>
int findid(const vc<t>&vs,const u&a){
	auto itr=find(all(vs),a);
	if(itr==vs.ed)return -1;
	else return itr-vs.bg;
}

template<class t>
void rtt(vc<t>&vs,int i){
	rotate(vs.bg,vs.bg+i,vs.ed);
}

//copied from yosupo's library
//PARTLY VERIFIED

//USACO 2022 January ptlatinum C

#define GEOF

#ifdef GEOF
using ld=long double;
//using ld=double;
const ld PI=acos(ld(-1));
#else
using ld=ll;
#endif
const ld eps=1e-9;
int sgn(ld a){return a<-eps?-1:(a>eps?1:0);}
int sgn(ld a,ld b){return sgn(a-b);}
/*
using pt=complex<ld>;
#define x real()
#define y imag()
*/
struct pt {
    ld x,y;
    //pt(ld _x = ld(0), ld _y = ld(0)) : x(_x), y(_y) {}
    pt():x(0),y(0){}
    pt(ld xx,ld yy):x(xx),y(yy){}
    pt operator+(const pt& r) const { return {x + r.x, y + r.y}; }
    pt operator-(const pt& r) const { return {x - r.x, y - r.y}; }
    pt operator*(const pt& r) const {
        return {x * r.x - y * r.y, x * r.y + y * r.x};
    }
    pt inv()const{
		ld d=norm();
		return {x/d,-y/d};
	}
    pt operator/(const pt&r)const{
		return operator*(r.inv());
	}

    pt operator*(const ld& r) const { return {x * r, y * r}; }
    pt operator/(const ld& r) const { return {x / r, y / r}; }

    pt& operator+=(const pt& r) { return *this = *this + r; }
    pt& operator-=(const pt& r) { return *this = *this - r; }
    pt& operator*=(const pt& r) { return *this = *this * r; }
    pt& operator/=(const pt& r) { return *this = *this / r; }
    pt& operator*=(const ld& r) { return *this = *this * r; }
    pt& operator/=(const ld& r) { return *this = *this / r; }

    pt operator-() const { return {-x, -y}; }

	static int cmp(const pt&a,const pt&b){
		int v=sgn(a.x,b.x);
		return v?v:sgn(a.y,b.y);
	}
    bool operator<(const pt& r) const {
        return cmp(*this,r)<0;
    }
    bool operator<=(const pt& r) const {
        return cmp(*this,r)<=0;
    }
    bool operator>(const pt& r) const {
        return cmp(*this,r)>0;
    }
    bool operator==(const pt& r) const { return sgn((*this - r).rabs()) == 0; }
    bool operator!=(const pt& r) const { return !(*this == r); }

    ld norm() const { return x * x + y * y; }
    ld rabs() const { return max(std::abs(x), std::abs(y)); }  // robust abs
    pair<ld, ld> to_pair() const { return {x, y}; }
    #ifdef GEOF
    ld abs() const { return sqrt(norm()); }
    ld arg() const { return atan2(y, x); }
    static pt polar(ld le, ld th) { return {le * cos(th), le * sin(th)}; }
	#endif
};
istream& operator>>(istream& is, pt& p){
	return is>>p.x>>p.y;
}
ostream& operator<<(ostream& os, const pt& p) {
    return os << "pt(" << p.x << ", " << p.y << ")";
}
ld norm(const pt&a){
	return a.norm();
}
#ifdef GEOF
ld abs(const pt&a){
	return sqrt(norm(a));
}
//XXII Opencup Gpt of Ural K
pt normalized(const pt&a){
	return a/abs(a);
}
ld arg(const pt&a){return a.arg();}
//normalize to [-PI,PI)
//Contest 2: ptKU Contest 1, ptTZ Summer 2022 Day 4
ld normarg(ld a){
	ld res=fmod(a+PI,2*PI);
	if(res<0)res+=PI;
	else res-=PI;
	return res;
}
//normalize to [0,2*PI)
//Multiuni2023-10-E
ld normarg_nonnegative(ld a){
	ld res=fmod(a,2*PI);
	if(res<0)res+=2*PI;
	return res;
}
//AOJ1183
//arg between ab
//assume given lengths are valid
ld arg(ld a,ld b,ld c){
	return acos(min(max((a*a+b*b-c*c)/(2*a*b),ld(-1)),ld(1)));
}
#endif
ld norm(const pt&a,const pt&b){
	return (a-b).norm();
}
ld dot(const pt&a,const pt&b){return a.x*b.x+a.y*b.y;}
ld crs(const pt& a,const pt& b){return a.x*b.y-a.y*b.x;}
ld crs(const pt& a,const pt& b,const pt& c){return crs(b-a,c-a);}
int ccw(const pt& a,const pt& b){return sgn(crs(a,b));}
int ccw(const pt& a,const pt& b,const pt& c){return ccw(b-a,c-a);}
//(-pi,0](0,pi]
int argtype(const pt&a){
	if(sgn(a.y)==0)return a.x<0?1:0;
	return a.y<0?0:1;
}
int argcmp(const pt&a,const pt&b){
	int at=argtype(a),bt=argtype(b);
	if(at!=bt)return at<bt?-1:1;
	return -ccw(a,b);
};
bool argless(const pt&a,const pt&b){return argcmp(a,b)<0;}
//(-2)[a,-1](0)[b,1](2)
int bet(pt a,pt b,pt c){
	pt d=b-a;
	ld e=dot(d,c-a);
	if(sgn(e)<=0)return sgn(e)-1;
	return sgn(e-norm(d))+1;
}
//AOJ0153
//三角形 abc に d が含まれるか?0-no,1-edge,2-in
int cont(pt a,pt b,pt c,pt d){
	if(ccw(a,b,c)==-1) swap(b,c);
	return min({ccw(a,b,d),ccw(b,c,d),ccw(c,a,d)})+1;
}
//(a,b) を結ぶ直線を考え,x 座標との交点の y 座標を求める
//(分子,分母)を返す
pair<ld,ld> xcut(const pt&a,const pt&b,ld x){
	return mp(a.y*(b.x-x)-b.y*(a.x-x),b.x-a.x);
}
//XXII Opencup Gpt of Ural K
pt rot90(pt a){
	return pt(-a.y,a.x);
}
#ifdef GEOF
ld xcutval(const pt&a,const pt&b,ld x){
	auto [p,q]=xcut(a,b,x);
	return p/q;
}
//AOJ1183
//Xmas2010 E
//-+ の 順で返す
//a の符号により,small/large が決まる
int qeq(ld a,ld b,ld c,ld&d,ld&e){
	if(sgn(a)==0){
		if(sgn(b)==0)return 0;
		d=-c/b;
		return 1;
	}
	ld f=b*b-4*a*c;
	if(sgn(f)<0)return 0;
	ld g=sqrt(max(f,ld(0)));
	d=(-b-g)/(2*a);
	e=(-b+g)/(2*a);
	return sgn(f)+1;
}
#else
pt normdir(pt a){
	if(a==pt(0,0))return a;
	int g=gcd(a.x,a.y);
	return pt(a.x/g,a.y/g);
}
#endif

ld area2(const vc<pt>&ps){
	ld res=0;
	rep(i,si(ps))res+=crs(ps[i],ps[(i+1)%si(ps)]);
	return res;
}

bool dbg=false;

//copied from old version
//USACO 2022 January ptlatinum C
//allow onedge vertices
vc<pt> convex(vc<pt> s,bool onedge){
	sort(all(s));
	s.erase(unique(all(s)),s.ed);
	sort(s.bg+1,s.ed,[&](pt a,pt b){
		int c=ccw(s[0],a,b);
		if(c)return c==1;
		else{
			if(onedge&&sgn(s[0].x-a.x)==0)
				return a.y>b.y;
			return bet(s[0],a,b)==2;
		}
	});
	vc<pt> t;
	rep(i,s.size()){
		int ss;
		while((ss=t.size())>=2){
			pt a=t[ss-2];
			pt b=t[ss-1];
			pt c=s[i];
			if(ccw(a,b,c)>=(onedge?0:1))
				break;
			t.pop_back();
		}
		t.pb(s[i]);
	}
	return t;
}

//UCUP 2-4-K
template<int L,class F>
auto ternary_min(ld l,ld r,F f){
	rep(_,L){
		ld m1=(l+l+r)/3;
		ld m2=(l+r+r)/3;
		if(f(m1)>f(m2))l=m1;
		else r=m2;
	}
	return mp(f(l),l);
}

ld maxdist(const vc<pt>&a,const vc<pt>&b){
	int n=si(a),m=si(b);
	if(n<=2||m<=2){
		ld res=0;
		for(auto p:a)for(auto q:b)chmax(res,norm(p,q));
		return res;
	}
	int i=MINi(a).b,j=MAXi(b).b;
	ld mx=norm(a[i],b[j]);
	rep(_,n+m){
		int p=(i+1)%n,q=(j+1)%m;
		if(ccw(a[p]-a[i],b[q]-b[j])>0)j=q;
		else i=p;
		chmax(mx,norm(a[i],b[j]));
	}
	return mx;
}

void slv(){
	int n;cin>>n;
	vc<pt> a(n);
	rep(i,n)cin>>a[i];
	int m;cin>>m;
	vc<pt> b(m);
	rep(i,m)cin>>b[i];
	a=convex(a,false);
	b=convex(b,false);
	
	const ld vmax=ten(6)+7;
	ld ans=inf,ansx=0,ansy=0;
	ternary_min<100>(-vmax,vmax,[&](ld tx){
		return ternary_min<100>(-vmax,vmax,[&](ld ty){
			vc<pt> c=b;
			for(auto&[x,y]:c){
				x+=tx;
				y+=ty;
			}
			ld val=maxdist(a,c);
			if(chmin(ans,val)){
				ansx=tx;
				ansy=ty;
			}
			return val;
		}).a;
	});
	print(sqrt(ans),-ansx,-ansy);
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	if(dbg){
		while(1)slv();
	}else{
		//int t;cin>>t;rep(_,t)
		slv();
	}
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3992kb

input:

3
1 5
2 4
6 8
2
1 3
1 6

output:

4.03112887414930683681 -3.00000009584532898940 -1.49999994523127570508

result:

ok n=3 m=2 err=0.000000

Test #2:

score: 0
Accepted
time: 2ms
memory: 3944kb

input:

1
5 1
1
4 9

output:

0.00000000000060096327 -1.00000000000024675422 7.99999999999945203165

result:

ok n=1 m=1 err=0.000000

Test #3:

score: 0
Accepted
time: 2ms
memory: 4020kb

input:

1
2 2
1
10 3

output:

0.00000000000060096336 7.99999999999945203165 1.00000000000024675422

result:

ok n=1 m=1 err=0.000000

Test #4:

score: 0
Accepted
time: 2ms
memory: 3940kb

input:

1
1 2
1
1 2

output:

0.00000000000001858620 -0.00000000000001314241 -0.00000000000001314241

result:

ok n=1 m=1 err=0.000000

Test #5:

score: 0
Accepted
time: 4ms
memory: 3820kb

input:

5
1 6
2 10
5 2
6 10
7 10
1
6 5

output:

4.40347873845242875849 1.50000000000006299019 -1.37499999999968572004

result:

ok n=5 m=1 err=0.000000

Test #6:

score: 0
Accepted
time: 3ms
memory: 3892kb

input:

1
7 3
6
2 9
7 6
4 1
8 8
3 9
1 9

output:

4.59512410488974508329 -2.91509433962242573823 2.59433962264156712358

result:

ok n=1 m=6 err=0.000000

Test #7:

score: 0
Accepted
time: 2ms
memory: 3860kb

input:

2
2 3
9 9
2
4 1
8 10

output:

9.30053761886920943996 0.50000072729268939996 -0.50000053334793684680

result:

ok n=2 m=2 err=0.000000

Test #8:

score: 0
Accepted
time: 3ms
memory: 3828kb

input:

1
9 8
8
10 6
6 8
3 4
10 9
5 7
2 7
5 3
5 10

output:

4.31386919778780594413 -2.69230769230847375925 -1.23076923076809756146

result:

ok n=1 m=8 err=0.000000

Test #9:

score: 0
Accepted
time: 2ms
memory: 3816kb

input:

3
7 3
4 9
7 1
1
6 2

output:

4.27200187265877400628 0.49999992892576261536 -3.00000002665283074452

result:

ok n=3 m=1 err=0.000000

Test #10:

score: 0
Accepted
time: 2ms
memory: 3876kb

input:

2
6 8
8 8
1
4 3

output:

1.00000000000033866790 -2.99999999999966133210 -5.00000000014172786859

result:

ok n=2 m=1 err=0.000000

Test #11:

score: 0
Accepted
time: 3ms
memory: 3872kb

input:

1
2 3
11
7 6
5 10
2 2
4 1
9 3
7 4
1 3
5 6
3 1
9 9
1 1

output:

5.65685424949239857185 2.99999988556911419547 2.00000011443090851965

result:

ok n=1 m=11 err=0.000000

Test #12:

score: 0
Accepted
time: 2ms
memory: 3884kb

input:

11
7 4
5 1
7 3
9 10
3 1
10 10
5 5
10 5
5 6
4 1
10 4
1
8 10

output:

5.70087712549570687888 1.49999997086678104035 4.50000002265914893825

result:

ok n=11 m=1 err=0.000000

Test #13:

score: 0
Accepted
time: 9ms
memory: 3864kb

input:

9
8 8
3 1
6 5
5 6
9 6
9 2
9 3
9 10
3 4
11
2 8
1 2
6 7
1 6
4 1
4 5
1 7
10 2
9 8
10 9
6 2

output:

10.96585609973073029838 -0.50000090288948529705 0.00000084645888417225

result:

ok n=9 m=11 err=0.000000

Test #14:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

1
8 9
5
8 2
9 7
10 6
3 10
8 1

output:

5.14781507049352184948 -2.50000036838095169721 -3.50000020465608935793

result:

ok n=1 m=5 err=0.000000

Test #15:

score: 0
Accepted
time: 2ms
memory: 4024kb

input:

1
2 5
3
6 10
6 5
5 5

output:

2.54950975679646445931 3.50000035707961021066 2.49999992858412490768

result:

ok n=1 m=3 err=0.000000

Test #16:

score: 0
Accepted
time: 3ms
memory: 4084kb

input:

8
3 9
5 9
8 2
3 2
2 3
6 10
2 5
8 4
2
6 1
2 8

output:

8.32165848854664022029 -1.50000012615077737022 -1.00000008109690472977

result:

ok n=8 m=2 err=0.000000

Test #17:

score: 0
Accepted
time: 22ms
memory: 3976kb

input:

96
499494 995347
917205 115724
615677 485675
26653 628830
290255 636019
436997 310488
679704 554538
836274 957304
523167 839393
156311 171726
69930 651786
817224 146624
576446 502999
448250 62722
233665 306365
158866 262089
119321 739022
740724 416112
447595 593338
896009 396447
197000 643460
732359...

output:

1237916.27993537697295778344 -44154.23339819574423970039 -45820.20369020559166983730

result:

ok n=96 m=85 err=0.000000

Test #18:

score: 0
Accepted
time: 16ms
memory: 3952kb

input:

99
257522 959200
592396 748566
183664 7040
814688 14427
587861 749501
257013 647974
574312 16452
303911 801221
273835 163180
320884 988776
240807 795947
942562 731067
373821 953920
143172 74694
539481 15429
684143 403399
387168 771412
46522 597152
511683 147921
958389 1583
942733 714163
774789 32821...

output:

1288871.16778142337341250823 -29975.50006581699898866589 -9263.00006086057495835462

result:

ok n=99 m=92 err=0.000000

Test #19:

score: 0
Accepted
time: 23ms
memory: 4096kb

input:

100
987841 173526
177982 166740
549515 522092
384826 507690
101387 672150
49976 800615
263841 244885
317357 360030
83752 360207
52473 896219
93778 10715
492695 855171
736451 599872
1405 199234
260020 787483
480774 125801
846063 137442
730974 808875
4697 513596
734335 772872
741817 525484
249698 1474...

output:

1212182.43911250528503842361 57834.08674358403146698038 25727.07544253067527151302

result:

ok n=100 m=96 err=0.000000

Test #20:

score: 0
Accepted
time: 88ms
memory: 3872kb

input:

100
2100 493261
2232 480924
2363 513583
4231 526960
5996 428721
7499 412811
9989 390221
14718 367273
19269 350934
34370 302009
36805 295415
75680 204256
83177 188051
84259 186130
88584 543060
92807 572895
100939 609000
101502 163596
101936 613024
105050 624874
108584 156500
109230 638827
111400 1537...

output:

1032223.02490716101806356164 58026.19226508812396758685 20246.69109833946013665695

result:

ok n=100 m=83 err=0.000000

Test #21:

score: 0
Accepted
time: 62ms
memory: 3932kb

input:

66
95860 272900
97306 254938
117654 220167
131357 199036
150957 318785
151093 362911
152746 380860
155133 169263
158495 427838
167614 471428
173305 494093
186930 517242
188000 142329
197122 532864
205961 899507
230549 551919
233463 928587
237597 102501
254306 999332
259764 557400
263409 558031
26877...

output:

987761.97199945392520703535 224224.99994420987664511813 -21726.50001348041786641829

result:

ok n=66 m=100 err=0.000000

Test #22:

score: 0
Accepted
time: 122ms
memory: 3896kb

input:

98
23339 492481
89014 480660
89041 432908
90903 386255
91839 377309
134955 357101
140159 546249
140713 575042
170884 602523
172201 282212
196218 882407
200781 903891
202717 911224
203781 619304
208527 929437
209385 931430
209829 219728
214483 940179
216525 157708
221247 951565
222331 626997
225762 9...

output:

1000001.38194524935829576862 -16724.78256427830548247471 4967.85406119355352938527

result:

ok n=98 m=99 err=0.000000

Test #23:

score: 0
Accepted
time: 78ms
memory: 3940kb

input:

88
25877 687813
31632 702872
50292 749437
58777 768460
60926 312678
61187 346434
62171 298892
63334 289745
67208 402050
73088 451930
75449 258737
77118 482674
77152 806056
81712 515955
83815 238185
84163 819202
92870 588484
98801 622179
106497 853280
111544 669489
112605 179371
114699 863818
133030 ...

output:

1012119.11881057439637743300 -147183.60958249255418195389 8191.84224334277648260638

result:

ok n=88 m=91 err=0.000000

Test #24:

score: 0
Accepted
time: 72ms
memory: 3876kb

input:

77
303632 539543
304231 548535
306013 483196
307296 571896
307669 478206
309536 575990
313039 102618
317759 94854
321820 596009
335628 618096
344252 66009
354055 293491
360439 57058
361107 141696
363089 634276
366149 635865
379856 421457
382611 45803
384214 385713
386625 448925
402881 653417
410695 ...

output:

1043521.24206793697419470845 -157896.39294954701000506248 65902.50284577365037819163

result:

ok n=77 m=80 err=0.000000

Test #25:

score: 0
Accepted
time: 75ms
memory: 3900kb

input:

97
2794 362191
4147 399220
4454 349686
6130 432943
6717 333182
6763 112567
10800 107497
12057 458770
18182 481566
22445 286502
22713 93363
28176 504839
31887 265270
35243 516538
38731 76253
49895 242059
51365 64668
64528 55827
67950 566520
79806 583152
84049 44162
90265 594464
111249 33641
122377 62...

output:

993406.36177826041313210226 20325.88960077000112924850 8484.77877817051781139668

result:

ok n=97 m=66 err=0.000000

Test #26:

score: 0
Accepted
time: 94ms
memory: 4084kb

input:

89
47942 182627
55836 169685
66878 154453
76686 141108
84417 131462
101401 112835
105496 109507
127132 395883
127138 419676
128075 475215
129083 503243
129988 363220
130044 526666
131560 535537
133757 331768
134256 549340
135613 94546
145931 599346
148304 254635
155338 629736
162849 229793
163518 65...

output:

1117550.71585252899433271523 13481.49999179253379644194 1764.50000712212013942448

result:

ok n=89 m=97 err=0.000000

Test #27:

score: 0
Accepted
time: 103ms
memory: 3964kb

input:

98
16284 502642
16633 493430
17800 515105
22765 550870
28059 586648
36346 613844
50719 638074
70086 456050
79472 684155
97022 711165
103050 336448
104891 383989
104938 723128
105132 311455
109161 443923
111816 251085
117512 740938
128560 188633
142349 159709
151508 142130
151783 785286
164551 800156...

output:

1023187.68441481844098461806 21894.86919316593544593275 21493.23893595838580772295

result:

ok n=98 m=92 err=0.000000

Test #28:

score: 0
Accepted
time: 101ms
memory: 3964kb

input:

97
174144 365544
175753 338535
176411 390960
179994 299289
180147 426730
182463 290428
184873 468930
191401 520692
193260 535025
195371 246795
198343 554865
204761 578268
209835 589959
212303 595491
213329 220953
220160 612606
220241 211257
224517 617663
261610 164554
280034 145374
298974 669061
307...

output:

1014748.12439221453769278014 -79822.82769343483988677690 26708.19044272220315150435

result:

ok n=97 m=96 err=0.000000

Test #29:

score: 0
Accepted
time: 107ms
memory: 3896kb

input:

95
98065 636830
103777 691006
113633 747583
127257 805793
133097 829409
139376 847000
145099 859891
174956 919356
179338 585491
180375 929035
188474 609821
204919 950405
208035 447744
217023 956198
242307 968209
244358 475478
252142 566321
264197 412819
276158 981100
280280 982412
284393 983205
3014...

output:

1027711.16079461811045803188 11106.51914834122113795445 5712.60236353654750374176

result:

ok n=95 m=95 err=0.000000

Test #30:

score: 0
Accepted
time: 28ms
memory: 4040kb

input:

996
499494 995347
917205 115724
615677 485675
26653 628830
290255 636019
436997 310488
679704 554538
836274 957304
523167 839393
156311 171726
69930 651786
817224 146624
576446 502999
448250 62722
233665 306365
158866 262089
119321 739022
740724 416112
447595 593338
896009 396447
197000 643460
73235...

output:

1352561.66275852625926745532 18438.40799460772320905733 -25.17113807256359579723

result:

ok n=996 m=985 err=0.000000

Test #31:

score: 0
Accepted
time: 28ms
memory: 4120kb

input:

999
257522 959200
592396 748566
183664 7040
814688 14427
587861 749501
257013 647974
574312 16452
303911 801221
273835 163180
320884 988776
240807 795947
942562 731067
373821 953920
143172 74694
539481 15429
684143 403399
387168 771412
46522 597152
511683 147921
958389 1583
942733 714163
774789 3282...

output:

1378487.82490125751576215407 2843.00016062585975529231 5769.99983584351542154067

result:

ok n=999 m=992 err=0.000000

Test #32:

score: 0
Accepted
time: 1528ms
memory: 4160kb

input:

993
615 519218
617 517469
619 515767
624 524431
626 525094
630 513100
642 527669
660 508605
660 529253
685 531414
730 499678
762 536468
779 537073
816 493023
842 491073
875 489905
927 488312
950 541893
1117 482527
1206 547427
1264 478680
1490 473007
1514 553162
1552 471495
1796 558255
1799 466169
18...

output:

1062252.79452922094287714572 4452.25150732915945495094 -12326.78957162132078728689

result:

ok n=993 m=976 err=0.000000

Test #33:

score: 0
Accepted
time: 1543ms
memory: 4168kb

input:

981
1017 566234
1019 563943
1020 567032
1023 559536
1043 557326
1061 555877
1082 554710
1082 572289
1125 552838
1140 577041
1182 550439
1237 548237
1237 582678
1308 546219
1326 586146
1388 544028
1463 590551
1535 540215
1577 594018
1640 537506
1833 532998
1882 531924
1963 603078
2143 607114
2165 526...

output:

1079230.20077716505090847932 7723.73863763874724419622 -10971.60098826277497874315

result:

ok n=981 m=990 err=0.000000

Test #34:

score: 0
Accepted
time: 1517ms
memory: 4128kb

input:

972
1349 512364
1364 516711
1379 504982
1380 518796
1420 499424
1423 523276
1427 523682
1435 497837
1442 524561
1523 489993
1538 530105
1631 483721
1639 534802
1672 535964
1736 479419
1835 475666
1879 540869
1957 471546
1963 542804
2053 468665
2088 545588
2169 466450
2256 464959
2621 459302
2840 456...

output:

1074931.55438590600533643737 7678.49986499331921141476 2282.50012674963372694137

result:

ok n=972 m=969 err=0.000000

Test #35:

score: 0
Accepted
time: 1559ms
memory: 4112kb

input:

1000
164 534631
166 533532
189 527791
212 537500
221 525573
299 542342
348 544665
367 518493
441 515154
491 551253
514 512559
589 555378
647 508575
774 561637
919 566166
934 501125
1205 573809
1259 493586
1476 488568
1559 486663
1612 485603
1625 584283
1852 589866
1938 479997
2063 594624
2139 476569...

output:

1081453.23508878551967882231 5571.00004478868772528344 -1775.99995470842598688233

result:

ok n=1000 m=998 err=0.000000

Test #36:

score: 0
Accepted
time: 1561ms
memory: 4184kb

input:

994
631 442590
641 444412
644 439051
686 450632
687 431990
699 430187
706 429189
728 452731
757 422171
771 420270
822 416597
843 457792
861 414434
881 459362
910 460435
967 410702
1043 465018
1049 408220
1198 470104
1212 403386
1311 401186
1320 474050
1346 474797
1444 477359
1483 397515
1518 396784
...

output:

1054401.72944967033845387050 -6981.94484394908427216109 -6433.85302241188723026966

result:

ok n=994 m=996 err=0.000000

Test #37:

score: 0
Accepted
time: 1547ms
memory: 4088kb

input:

991
1850 564831
1852 562297
1855 559736
1872 557599
1876 569480
1967 549168
1982 573517
2012 574537
2034 544935
2080 542038
2104 577105
2223 535854
2469 525460
2509 523828
2529 523133
2615 590300
2668 591588
2674 518694
2683 518423
2739 516933
2856 595782
2875 513379
3026 510561
3182 602250
3238 507...

output:

1060980.93806138657691917615 8294.00492296560660143712 -6497.23304009625165456043

result:

ok n=991 m=995 err=0.000000

Test #38:

score: 0
Accepted
time: 1556ms
memory: 4132kb

input:

994
425 477653
426 481113
427 472213
430 482938
434 484599
437 485348
441 486079
486 490258
489 466458
534 493880
603 459742
614 499472
651 457772
681 503775
705 455761
762 508666
876 449933
997 517849
1051 445577
1089 521053
1128 443937
1168 523373
1212 524660
1225 442009
1422 529769
1497 531584
19...

output:

1082267.45544306992496785824 -1421.63566833729857030733 14387.42195584417897968876

result:

ok n=994 m=994 err=0.000000

Test #39:

score: 0
Accepted
time: 1560ms
memory: 4108kb

input:

991
1164 448671
1172 446635
1180 445056
1183 451382
1184 444270
1225 456408
1235 457554
1238 438265
1247 458200
1312 430347
1345 462205
1366 425285
1416 420916
1450 418161
1527 412566
1608 406816
1648 404489
1689 402226
1716 476811
1752 478195
1929 484629
1953 394091
2074 488972
2087 390190
2125 490...

output:

1072254.61133538614410554146 17892.00013335694983673818 -7286.00012918933411754097

result:

ok n=991 m=1000 err=0.000000

Test #40:

score: 0
Accepted
time: 1539ms
memory: 4240kb

input:

989
1041 516925
1043 521187
1046 522648
1050 515202
1055 514689
1081 535143
1098 539942
1127 547011
1139 548732
1170 552696
1257 563452
1278 495918
1280 566051
1295 494496
1316 568966
1360 489985
1368 572937
1435 484947
1517 479665
1525 479171
1535 582555
1553 477552
1588 475994
1603 584808
1756 589...

output:

1071350.16165455913926507492 11952.50013817100014801298 4380.99984665089199786792

result:

ok n=989 m=992 err=0.000000

Test #41:

score: 0
Accepted
time: 1555ms
memory: 4184kb

input:

1000
1195 462128
1201 463009
1234 457015
1237 456705
1249 466226
1269 454141
1285 468002
1329 449635
1334 469813
1347 470254
1352 448262
1392 446152
1447 473533
1485 443138
1496 475073
1535 476212
1587 477569
1755 436423
1755 481897
1782 435783
1849 484151
2011 430504
2052 429700
2060 489009
2077 48...

output:

1056333.78573878029726529348 4025.55327848860372230710 3532.07462409397101321673

result:

ok n=1000 m=991 err=0.000000

Test #42:

score: 0
Accepted
time: 1573ms
memory: 4144kb

input:

993
614 483119
615 482738
651 478578
710 473392
717 497183
738 499968
763 470294
829 509584
836 466495
881 513317
903 463452
912 515293
985 518319
1055 521174
1087 522385
1138 453322
1151 524359
1171 452247
1298 448166
1418 444353
1469 442962
1555 440623
1633 438708
1804 434526
1821 434159
1923 4322...

output:

1075574.38650258128416226100 7087.80568674702706655211 4861.12892616092863296018

result:

ok n=993 m=994 err=0.000000

Test #43:

score: 0
Accepted
time: 1571ms
memory: 4020kb

input:

997
75 449509
76 446631
78 450295
95 432993
109 456855
125 458612
152 461005
184 463086
207 464565
228 423968
231 465884
255 423079
342 421238
355 471781
406 474202
412 474480
480 476787
696 414429
906 490192
1020 493693
1040 408413
1063 494968
1201 498932
1344 502970
1399 504512
1546 508208
1624 39...

output:

1071140.64965616220376887213 3538.08364279326477119803 3842.17600763173842715048

result:

ok n=997 m=997 err=0.000000

Test #44:

score: 0
Accepted
time: 1547ms
memory: 4296kb

input:

989
459 533612
460 526411
462 541026
464 522019
470 549472
473 549914
479 518626
493 516263
524 511559
550 508138
563 507308
572 506895
597 559114
633 561642
721 500997
732 565245
804 567350
805 498117
894 495241
1043 573673
1146 576117
1185 486712
1227 485630
1384 580969
1537 479019
1788 473674
186...

output:

1060385.32755179336936635082 4035.97993104926919372133 -2002.21621449948515791828

result:

ok n=989 m=996 err=0.000000

Test #45:

score: 0
Accepted
time: 1555ms
memory: 4220kb

input:

997
1316 518316
1322 521512
1325 508449
1343 505459
1346 526415
1365 502360
1365 529214
1382 499983
1392 498868
1432 496132
1475 493712
1495 539863
1516 491426
1580 544084
1635 546558
1669 483232
1684 547717
1713 481004
1751 479253
1832 476553
1973 473579
2087 556581
2175 469575
2238 468498
2420 465...

output:

1070746.73966582779405598558 15036.00000550057169768081 3622.99999410470311111965

result:

ok n=997 m=999 err=0.000000

Test #46:

score: 0
Accepted
time: 1559ms
memory: 4100kb

input:

994
2205 552253
2206 552689
2209 552951
2215 548753
2259 543640
2274 542257
2357 539254
2374 561411
2427 563387
2513 566395
2548 532374
2602 569239
2624 569935
2656 528952
2811 524516
2861 523164
2884 577414
2910 578134
2962 579377
3067 517953
3070 581791
3188 584059
3189 514970
3302 586224
3505 589...

output:

1069818.05367184840588379302 13613.35982782030042237409 -1991.94366434659873887902

result:

ok n=994 m=999 err=0.000000

Test #47:

score: 0
Accepted
time: 1531ms
memory: 4076kb

input:

963
834 543361
836 535792
849 552072
850 552501
874 531035
883 556864
888 557488
914 560360
930 561193
935 527487
1037 524408
1240 577124
1244 518226
1280 578701
1319 516158
1439 583355
1462 512721
1525 511304
1584 587278
1608 509538
1817 592099
1828 505026
1948 594421
2073 596472
2134 498784
2135 5...

output:

1064784.73614964766306911770 2330.39517099106062225644 7032.76207084154214577154

result:

ok n=963 m=993 err=0.000000

Test #48:

score: 0
Accepted
time: 1548ms
memory: 4308kb

input:

985
2582 537826
2618 542713
2624 531735
2651 528037
2673 525287
2751 519638
2816 515139
2898 510087
2954 554627
3019 503015
3098 558595
3109 558889
3123 497277
3155 559944
3321 487951
3479 480516
3583 476304
3636 474522
3636 569898
3700 472612
3896 467080
3942 465895
3960 576596
4113 461584
4209 581...

output:

1069365.25385729188360528497 -3085.07195017484055510337 10396.21136461483719415355

result:

ok n=985 m=997 err=0.000000

Test #49:

score: 0
Accepted
time: 1553ms
memory: 4104kb

input:

987
1181 498215
1183 500828
1194 494762
1202 506979
1212 508963
1252 514679
1296 487535
1299 487332
1312 486465
1339 524535
1361 526912
1373 527965
1398 529760
1444 479976
1444 532681
1507 536063
1530 536924
1556 474716
1868 548605
2021 553300
2034 455842
2147 556616
2234 558875
2262 449370
2294 560...

output:

1074840.58267308097254044696 12125.72313247726333784726 13972.04666307746144049418

result:

ok n=987 m=990 err=0.000000

Test #50:

score: 0
Accepted
time: 3ms
memory: 3876kb

input:

3
15 4
3 4
19 16
2
9 15
15 15

output:

12.52996408614171707039 0.99999998827374063815 5.00000002149824502966

result:

ok n=3 m=2 err=0.000000

Test #51:

score: 0
Accepted
time: 3ms
memory: 3940kb

input:

14
9 1
10 1
7 20
10 16
14 5
17 4
7 12
20 13
1 3
20 17
7 10
6 1
6 15
11 11
4
4 13
20 13
16 13
15 13

output:

18.84807682497078737231 1.50000033027467925351 2.99999917431329571685

result:

ok n=14 m=4 err=0.000000

Extra Test:

score: 0
Extra Test Passed