oj.uz

Submission #1109228

# Submission time Handle Problem Language Result Execution time Memory
1109228 2024-11-06T08:30:56 Z Gourougourou Plot (POI11_wyk) C++17
0 / 100
 30000 ms 3780 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<double,double> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
#define x first
#define y second
const double EPS = 1e-8;


double dist(pll a, pll b) {
    double in = (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
    return sqrt(in);
}
pair<pll,double> maxDist(vpll v) {
    double ans = 0;
    pll a = v[0];
    for (pll i : v) {
        for (pll j : v) {
            double res = dist(i,j);
            if (res > ans) {
                ans = res;
                a = {(i.x+j.x)/2,(i.y+j.y)/2};
            }
        }
    }
    return {a,ans};
}

vpll ok(int n, int m, vpll v, double k) {
    vpll ans;
    int ind = 0;
    while (ind < n) {
        int cur = ind, prev = cur;
        while (cur < n-1 && maxDist(vpll(v.begin()+ind,v.begin()+cur+1)).y <= 2*k) {
            prev = cur;
            int dif = cur-ind+1;
            cur = min(cur+dif, n-1);
        }
        ll lo = prev, hi = cur;
        while (lo < hi) {
            ll mid = (lo+hi+1)/2;
            auto p = maxDist(vpll(v.begin()+ind, v.begin()+mid+1));
            if (p.y <= 2*k) lo = mid;
            else hi = mid-1;
        }
        ans.push_back(maxDist(vpll(v.begin()+ind, v.begin()+lo+1)).x);
        ind = lo+1;
    }
    return ans.size() <= m ? ans : vpll();
}

int main() {
    int n, m; cin >> n >> m;
    vpll v(n);
    for (pll &p : v) cin >> p.x >> p.y;
    cout << maxDist(v).y << '\n';
    double lo = 0, hi = 1e18;
    while (hi-lo > EPS) {
        double mid = (hi+lo)/2;
        if (ok(n,m,v,mid).size()) hi = mid;
        else lo = mid;
    }
    cout << hi << '\n';
    vpll ans = ok(n,m,v,hi);
    cout << fixed << setprecision(7);
    cout << ans.size() << '\n';
    for (pll p : ans) cout << p.x << ' ' << p.y << '\n';
}

Compilation message

wyk.cpp: In function 'vpll ok(int, int, vpll, double)':
wyk.cpp:52:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<double, double> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |     return ans.size() <= m ? ans : vpll();
      |            ~~~~~~~~~~~^~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 8.0

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

Subtask #6
0 / 8.0

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

Subtask #7
0 / 8.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 8.0

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

Subtask #10
0 / 8.0

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

Subtask #11
0 / 8.0

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

Subtask #12
0 / 8.0

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

Subtask #13
0 / 8.0

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