Submission #1108963

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1108963	2024-11-05T18:03:56 Z	Gourougourou	Plot (POI11_wyk)	C++17	0 / 100	30000 ms	7276 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;


ll dist(pll a, pll b) {
    return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)+(a.y-b.y);
}
pair<pll,ll> maxDist(vpll v) {
    ll ans = 0;
    pll a = {0,0};
    for (pll i : v) {
        for (pll j : v) {
            ll 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, ll k) {
    vpll ans;
    vpll cur;
    pll prev = {-1,-1};
    for (int i = 0; i<n; ++i) {
        cur.push_back(v[i]);
        auto p = maxDist(cur);
        if (p.y > 4*k) {
            ans.push_back(prev);
            cur = {v[i]};
        }
        prev = p.x;
    }
    if (!cur.empty()) ans.push_back(prev);
    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;
    double lo = 0, hi = 19;
    while (hi-lo > EPS) {
        double mid = (hi+lo)/2;
        if (ok(n,m,v,mid).size()) hi = mid;
        else lo = mid;
    }
    vpll ans = ok(n,m,v,hi);
    cout << fixed << setprecision(14);
    cout << sqrt(hi) << '\n';
    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, ll)':
wyk.cpp:45: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]
   45 |     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	1 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	3 ms	336 KB	Nieprawidlowa wartosc r
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 8.0

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

Subtask #7
0 / 8.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 8.0

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

Subtask #10
0 / 8.0

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

Subtask #11
0 / 8.0

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

Subtask #12
0 / 8.0

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

Subtask #13
0 / 8.0

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