## 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 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);
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 {
}
}

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