Gigel îşi imaginează lumea în varianta 2d, adică reprezentată în sistem de coordonate cartezian XOY. Fiecare persoană din grupul celor N prieteni ai săi este reprezentată în plan printr-un punct identificat prin abscisa şi ordonata sa. În lumea sa 2d, plouă ca în Anglia, iar picăturile de ploaie pică paralel cu axa OY, de la o înălţime infinită. Ca să îi ferească pe prietenii săi de ploaie, îşi propune să le construiască apărători pe care le va reprezenta pe hartă prin segmente de dreaptă.

Cerința

Ştiind că nu poate să deseneze pe hartă decât segmente de lungimi egale, determinaţi care este lungimea minimă a unui segment astfel încât trasând cel mult K segmente, toți cei N prieteni ai săi să fie protejați de ploaie.

Date de intrare

Fişierul de intrare 2d.in conţine:

pe prima linie numerele naturale N şi K;
pe următoarele N linii se află perechi de numere reale x y, cu exact trei zecimale fiecare, reprezentând abscisa şi ordonata punctului corespunzător fiecărui prieten al lui Gigel;

Date de ieșire

Fişierul de ieşire 2d.out va conţine pe prima linie un singur număr real, cu trei zecimale reprezentând lungimea minimă a unui segment din cele trasate de Gigel.

Restricții și precizări

1 ≤ K < N ≤ 200000
-1000000.000 ≤ x,y ≤ 1000000.000
Lungimea minimă a unui segment pe care îl va trasa Gigel este 1.000
Rezultatul va fi afişat cu o eroare de cel mult 0.001
Un segment trasat între punctele (x1, y1) şi (x2, y2) protejează toate punctele de pe segment şi din semiplanul “de sub” dreapta ce trece prin aceste puncte şi care au abscisele în intervalul închis [x1, x2].

Exemplu

2d.in

5 3
-5.000 1.000
-2.000 3.000
3.000 2.000
3.000 -2.000
1.000 2.000

2d.out

2.000

Explicație

O posibilitate de trasare a segmentelor ar fi:

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema 2d:

/*************************
*O(N log N + N log diffx)*
*************************/

#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cassert>
using namespace std;

#define MAXN 200100

char S[100];
int A[MAXN];
int N, K, i, Left, Right, Mid, Sol, Poz, sign;

bool Check(int Rez)
{
    int Last = -2000000000;
    int Nr = 0;

    for (int i = 1; i <= N; ++i){
        if (A[i] <= Last)
            continue;
        Last = A[i] + Rez;
        ++Nr;
        if (Nr > K) break;
    }
    return (Nr <= K);
}

int main()
{
    freopen("2d.in","r",stdin);
    freopen("2d.out","w",stdout);

    scanf("%d %d\n", &N, &K);
    assert(1<=K && K < N && N<=200000);
    for (i = 1; i <= N; ++i){
        gets(S);
        Poz = 0;
        if (S[0] == '-'){
            sign = -1;
            ++Poz;
        }
        else
            sign = 1;
        A[i] = 0;
        while (S[Poz] != ' '){
            if (S[Poz] == '.')
                ++Poz;
            A[i] = A[i] * 10 + S[Poz] - '0';
            ++Poz;
        }
        A[i] *= sign;
    }

    sort(A+1, A+N+1);

    Left = 1000; Right = 2000000000; Sol = 1000;
    while (Left <= Right){
        Mid = (Left + Right) / 2;
        if (Check(Mid)) {
            Sol = Mid;
            Right = Mid - 1;
        }
        else
            Left = Mid + 1;
    }

    printf("%d.%.3d\n", Sol / 1000, Sol % 1000);

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #705 2d

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #705 2d de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #705 2d