oj.uz

Submission #688285

# Submission time Handle Problem Language Result Execution time Memory
688285 2023-01-27T09:46:33 Z browntoad Plot (POI11_wyk) C++14
84 / 100
 30000 ms 22968 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pdd pair<double ,double>
#define pcc pair<char, char> 
#define endl '\n'
//#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif

const ll inf = 1ll<<60;
const int iinf=2147483647;
const ll mod = 1e9+7;
const ll maxn=1e5+5;
const double PI=acos(-1);

ll pw(ll x, ll p, ll m=mod){
    ll ret=1;
    while (p>0){
        if (p&1){
            ret*=x;
            ret%=m;
        }
        x*=x;
        x%=m;
        p>>=1;
    }
    return ret;
}

ll inv(ll a, ll m=mod){
    return pw(a,m-2);
}

//=======================================================================================
const int mxpw = 18;
int n, m; 
const double eps = 1e-8;
struct Point{
	double x, y;
	void operator =(Point b){
		x=b.x;
		y=b.y;
	}
	bool operator <(Point b){
		if (abs(x-b.x)<eps) return y<b.y;
		return x<b.x;
	}
	Point operator +(Point b){
		return {x+b.x, y+b.y};
	}
	Point operator -(Point b){
		return {x-b.x, y-b.y};
	}
	Point operator *(double k){
		return {x*k, y*k};
	}
	double dot(Point a, Point b){
		return a.x*b.x+a.y*b.y;
	}
	double cross(Point a, Point b){
		return a.x*b.y-a.y*b.x;
	}
	double dis2(Point a, Point b){
		return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
	}
	Point midpoint(Point a, Point b){
		return (a+b)*0.5;
	}
	pair<Point, Point> perpbisector(pair<Point, Point> a){
		Point temp = a.s-a.f;
		temp = {temp.y, -temp.x};
		return {midpoint(a.f, a.s), midpoint(a.f, a.s)+temp};
	}
	Point intersect(pair<Point, Point> a, pair<Point, Point> b){
		if (abs(cross(a.s-a.f, b.s-b.f)) < eps) assert(0);
		double temp = cross(b.f-a.f, a.s-a.f);
		temp = temp / (temp + cross(a.s-a.f, b.s-a.f));
		return b.f+((b.s-b.f)*temp);
	}
	pair<Point, double> circum(Point a, Point b, Point c){
		// if a, b, c are collinear
		if (b<a) swap(a, b);
		if (c<a) swap(a, c);
		if (c<b) swap(b, c);
		Point ret;
		if (abs(cross(b-a, c-a))<eps){
			ret=midpoint(b, c);
		}
		else {
			ret=intersect(perpbisector({a, b}), perpbisector({a, c}));
		}
		return {ret, dis2(ret, b)};
	}
}point;



vector<Point> vc;
vector<Point> tmpvc;
pair<Point, double> triv(vector<Point> &t){
	if (SZ(t)==0){
		return {{0, 0}, 0};
	}
	if (SZ(t)==1){
		return {t[0], 0};
	}
	if (SZ(t)==2){
		Point tv;
		tv=point.midpoint(t[0], t[1]);
		return {tv, point.dis2(tv, t[0])};
	}
	if (SZ(t)==3){
		return point.circum(t[0], t[1], t[2]);
	}
	assert(0);
}
pair<Point, double> welzl(vector<Point> &t, int id){
	if (id==-1 || SZ(t)==3){
		return triv(t);
	}
	pair<Point, double> temp = welzl(t, id-1);
	if (point.dis2(temp.f, tmpvc[id]) > temp.s){
		vector<Point> t2;
		REP(i, SZ(t)) t2.pb(t[i]);
		t2.pb(tmpvc[id]);
		temp = welzl(t2, id-1);
		t2.clear();
		t2.shrink_to_fit();
		return temp;
	}
	else return temp;
	
}
pair<Point, double> minenclosingcircle(int l, int r){
	tmpvc.clear();
	tmpvc.shrink_to_fit();
	FOR(i, l, r+1) tmpvc.pb(vc[i]);
	random_shuffle(ALL(tmpvc));
	vector<Point> tmp;
	pair<Point, double> cur = welzl(tmp, SZ(tmpvc)-1);
	return cur;
}

vector<Point> res;
bool check(double g){
	res.clear();
	res.shrink_to_fit();
	int cur = 0, cnt = 1;
	pair<Point, double> tmp;
	int bsl=0, bsr=0, bsmid;
	while(cnt<=m){
		REP(j, mxpw){
			if ((1<<j)+cur-1>=n-1){
				tmp = minenclosingcircle(cur, n-1);
				if (tmp.s<=g){
					res.pb(tmp.f);
					return 1;
				}
				else {
					bsl=(1<<(j-1))-1+cur;
					bsr=n-1;
					break;
				}
			}
			else{
				tmp = minenclosingcircle(cur, cur+(1<<j)-1);
				if (tmp.s>g){
					bsl=(1<<(j-1))-1+cur;
					bsr=(1<<j)-1+cur;
					break;
				}
			}
		}
		while(bsl<bsr){
			bsmid = (bsl+bsr+1)/2;
			tmp = minenclosingcircle(cur, bsmid);
			if (tmp.s>g){
				bsr=bsmid-1;
			}
			else bsl=bsmid;
		}
		tmp = minenclosingcircle(cur, bsl);
		res.pb(tmp.f);
		cur=bsl+1;
		cnt++;
	}
	return 0;
}
signed main (){
    IOS();
    cin>>n>>m;
    cout<<fixed<<setprecision(10);
    vc.resize(n);
    REP(i, n){
    	cin>>vc[i].x>>vc[i].y;
    }
    double l=0.0, r=2e12;
    double mid;
    double p=-1;
    REP(k, 90){
    	mid = (l+r)/2;
    	if (check(mid)){
    		p=mid;
    		r=mid;
    	}
    	else {
    		l=mid;
    	}
    }
    check(p);
    cout<<sqrt(p)<<endl;
    cout<<SZ(res)<<endl;
    REP(i, SZ(res)){
    	cout<<res[i].x<<' '<<res[i].y<<endl;
    }
}
/*
2:53
*/

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 212 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 348 KB Output is correct
2 Correct 7 ms 540 KB Output is correct

Subtask #6
8.0 / 8.0

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

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 516 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 516 KB Output is correct
2 Correct 146 ms 468 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 1476 KB Output is correct
2 Correct 649 ms 1476 KB Output is correct
3 Correct 601 ms 1460 KB Output is correct

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6935 ms 11516 KB Nieprawidlowa wartosc r
2 Halted 0 ms 0 KB -

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13051 ms 5168 KB Output is correct
2 Correct 25130 ms 22968 KB Output is correct
3 Correct 7220 ms 9152 KB Output is correct

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 30037 ms 22796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1199 ms 22748 KB Output is correct
2 Correct 7562 ms 8048 KB Output is correct
3 Correct 10063 ms 22736 KB Output is correct