Submission #687592

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
687592	2023-01-26T15:48:20 Z	balbit	Plot (POI11_wyk)	C++14	100 / 100	19116 ms	65536 KB

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 1e5+5;

struct Pt{
	double x,y;
	Pt operator - (const Pt & b) {
		return {x-b.x, y-b.y};
	}
	Pt operator + (const Pt & b) {
		return {x+b.x, y+b.y};
	}
	Pt operator * (double d) {
		return {d*x, d*y};
	}
	bool operator < (const Pt & b) {
		return make_pair(x,y) < make_pair(b.x, b.y);
	}
	bool operator == (const Pt & b) {
		return make_pair(x,y) == make_pair(b.x, b.y);
	}
	double operator ^ (Pt b) {
		return x * b.y - y * b.x;
	}
	double len() {
		return x*x+y*y;
	}
	Pt rot90(){
		return {-y,x};
	}
	void dump(){
		cerr<<"("<<x<<", "<<y<<")"<<endl;
	}
	void in(){
		cin>>x>>y;
	}
};

double eps = 1e-8;

struct Circle{
	Pt o; double R;
	bool contains(Pt p) {
		return (o - p).len() <= R+eps;
	}
	void dump(){
		cerr<<"Cir: "<<o.x<<" "<<o.y<<"  "<<sqrt(R)<<endl;
	}
};

Pt BAD = {-1029.44342, 10289.313131};

Pt its(Pt a, Pt b, Pt c, Pt d) {
	Pt ab = b-a, ac = c-a, ad = d-a, cd = d-c;
	if ((ab ^ cd) == 0) return BAD; // parallel lines, don't really care about intersection
	double rat = (ac ^ ab) / ((ac ^ ab) + (ab ^ ad));
	return c + (cd) * rat;
}

Pt midpoint(Pt a, Pt b) {
	return (a + b) * 0.5;
}

Circle getcir(vector<Pt> v){
	sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());
	if (SZ(v) == 3) {
		Pt a=v[0],b=v[1],c=v[2];
		Pt ab2 = midpoint(a,b), bc2 = midpoint(b,c);
		Pt abr = (b-a).rot90() + ab2, bcr = (c-b).rot90() + bc2;
		Pt O = its(ab2, abr, bc2, bcr);
		if (O == BAD) {
			O = midpoint(v[0], v[2]);
		}
		return {O, (O - v[0]).len()};
	}
	else if (SZ(v) == 2) {
		Pt O = midpoint(v[0], v[1]);
		return {O, (O-v[0]).len()};
	}else if (SZ(v) == 1){
		return {v[0], 0};
	}else {
		return {BAD, 0};
	}
}

namespace WW{
	vector<Pt> v;

	Circle Weltzl(int idx, vector<Pt> r){
		if (idx < 0 || SZ(r) == 3) {
			bug("Hmm", idx, SZ(r));
			Circle rr = getcir(r);
			rr.dump();
			return rr;
		}else{
			Pt pp = v[idx]; 
			Circle D = Weltzl(idx-1,r);
			if (D.contains(pp)) return D;
			else {
				r.push_back(pp);
				return Weltzl(idx-1,r);
			}
		}
	}
}

Pt A[maxn];

map<pii, Circle> memo;

Circle getenc(int L, int R){
	if (L == R) return Circle{A[L], 0};
	bug("in");
	if (memo.count({L,R})) return memo[{L,R}];
	WW::v.clear(); 
	FOR(i,L,R+1) {
		WW::v.push_back(A[i]);
	}
	random_shuffle(ALL(WW::v));



	memo[{L,R}] = WW::Weltzl(R-L, vector<Pt>());
	bug("out");
	return memo[{L,R}];
}


signed main(){
    IOS();


    // Pt a = {2,0}, b = {0,4}, c = {4,4}, d = {3,0};
    // Circle cc = getcir({a,b,c});
    // cc.dump();
    // Pt I = its(a,b,c,d);
    // I.dump();

    // WW::v = {a,b,c,d};
    // Circle cc = WW::Weltzl(3, vector<Pt>());
    // cc.o.dump();
    // bug(cc.R);

	int n,M; cin>>n>>M;

	REP(i,n) A[i].in();

	double dl = 0, dr = 9e12;

	vector<pii> ans;

	REP(round, 100) {
		double dm = (dl + dr) / 2;
		bool OK = 0;
		int at = 0;
		int took = 0;

		vector<pii> pairs;
		pairs.clear();

		while (at < n) {
			if (took >= M) {
				OK = 0; break;
			}
			int fac = 1;
			for (; at + fac <= n; fac *= 2) {
				if (getenc(at, min(at + fac, n) - 1).R > dm) break;
			}

			int bl = at + fac/2, br = min(at + fac, n) - 1 + 1;
			while (bl != br) {
				int bm = (bl + br) / 2;
				if (getenc(at, bm).R > dm) {
					br = bm;
				}else{
					bl = bm + 1;
				}
			}
			pairs.pb({at, bl-1});
			at = bl;
			++took;
		}

		if (at >= n) OK = 1;

		bug(dl, dr, dm, OK);
		bug(at, took);
		if (OK) {
			bug(SZ(pairs));

			ans = pairs;
			dr = dm;
		}else{
			dl = dm;
		}
	}
	cout<<setprecision(10)<<fixed;
	cout<<sqrt(dl)<<endl;
	cout<<SZ(ans)<<endl;
	for (pii p : ans) {
		bug(p.f, p.s);
		Circle gt = getenc(p.f, p.s);
		cout<<gt.o.x<<' '<<gt.o.y<<endl;
	}

}

Subtask #1
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	212 KB	Output is correct
2	Correct	8 ms	284 KB	Output is correct

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	212 KB	Output is correct
2	Correct	4 ms	340 KB	Output is correct

Subtask #4
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	460 KB	Output is correct
2	Correct	60 ms	492 KB	Output is correct

Subtask #5
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	173 ms	1140 KB	Output is correct
2	Correct	2 ms	468 KB	Output is correct

Subtask #6
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	460 ms	1708 KB	Output is correct
2	Correct	366 ms	1592 KB	Output is correct

Subtask #7
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	268 ms	1408 KB	Output is correct

Subtask #8
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	186 ms	1184 KB	Output is correct
2	Correct	244 ms	1224 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2033 ms	6872 KB	Output is correct
2	Correct	3253 ms	9768 KB	Output is correct
3	Correct	4658 ms	14028 KB	Output is correct

Subtask #10
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2431 ms	17200 KB	Output is correct
2	Correct	4950 ms	22888 KB	Output is correct

Subtask #11
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13489 ms	55952 KB	Output is correct
2	Correct	13060 ms	50244 KB	Output is correct
3	Correct	7383 ms	45620 KB	Output is correct

Subtask #12
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6875 ms	32404 KB	Output is correct
2	Correct	6758 ms	31428 KB	Output is correct
3	Correct	19116 ms	65536 KB	Output is correct
4	Correct	2533 ms	28728 KB	Output is correct

Subtask #13
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	150 ms	22464 KB	Output is correct
2	Correct	10517 ms	65304 KB	Output is correct
3	Correct	3228 ms	29080 KB	Output is correct

Submission #687592

Compilation message