## Submission #688464

# Submission time Handle Problem Language Result Execution time Memory
688464 2023-01-27T13:29:11 Z browntoad Plot (POI11_wyk) C++14
100 / 100
28415 ms 24872 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 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-11;
struct Point{
double x, y;
void operator =(Point b){
x=b.x;
y=b.y;
}
bool operator <(Point b){
if (x==b.x) 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){
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)) < 0){
ret=midpoint(a, c);
}
else {
ret=intersect(perpbisector({a, b}), perpbisector({a, c}));
}
return {ret, dis2(ret, a)};
}
}point;

vector<Point> vc;
vector<Point> tmpvc;
pair<Point, double> triv(vector<Point> &t){
if (SZ(t)==0){
return {{5, 5}, 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 + eps){
vector<Point> t2;
REP(i, SZ(t)) t2.pb(t[i]);
t2.pb(tmpvc[id]);
temp = welzl(t2, id-1);
return temp;
}
else return temp;

}
pair<Point, double> minenclosingcircle(int l, int r){
tmpvc.clear();
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();
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+eps){
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+eps){
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+eps){
bsr=bsmid-1;
}
else bsl=bsmid;
}
tmp = minenclosingcircle(cur, bsl);
res.pb(tmp.f);
cur=bsl+1;
assert(cur<n);
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=3e12;
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 0 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 11 ms 332 KB Output is correct
2 Correct 6 ms 340 KB Output is correct

#### Subtask #5 8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 540 KB Output is correct
2 Correct 6 ms 540 KB Output is correct

#### Subtask #6 8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 348 KB Output is correct
2 Correct 86 ms 472 KB Output is correct

#### Subtask #7 8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 512 KB Output is correct

#### Subtask #8 8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 516 KB Output is correct
2 Correct 139 ms 520 KB Output is correct

#### Subtask #9 8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 1364 KB Output is correct
2 Correct 590 ms 1460 KB Output is correct
3 Correct 472 ms 1456 KB Output is correct

#### Subtask #10 8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6724 ms 10564 KB Output is correct
2 Correct 5589 ms 10612 KB Output is correct

#### Subtask #11 8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12415 ms 20800 KB Output is correct
2 Correct 23702 ms 21340 KB Output is correct
3 Correct 4991 ms 7296 KB Output is correct

#### Subtask #12 8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27296 ms 20804 KB Output is correct
2 Correct 28415 ms 20688 KB Output is correct
3 Correct 13474 ms 8652 KB Output is correct
4 Correct 6592 ms 20696 KB Output is correct

#### Subtask #13 8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1036 ms 20704 KB Output is correct
2 Correct 5414 ms 24872 KB Output is correct
3 Correct 13738 ms 20704 KB Output is correct