Aiuto per The Dutch Farmer (ois_tulips2)

Aiuto
1

Ciao a tutti, ho bisogno di aiuto per risolvere il problema The Dutch Farmer.

Guardando i casi d’esempio, ho scoperto che un tulipano è valido quando è all’interno di esattamente due delle semicirconferenze con i lati del rettangolo come diametro, ma mi dà output errato solo per l’ultimo testcase.

Ecco il mio codice:

// NOTE: it is recommended to use this even if you don't understand the following code.

#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

struct point
{
    double x, y;
};

int main()
{
    // uncomment the two following lines if you want to read/write from files
    //ifstream cin("/Users/Riccardo/Desktop/Coding/olinfo/OII4/input.txt");

    point topLeft, topRight, bottomRight, bottomLeft;
    cin >> topLeft.x >> topLeft.y;
    cin >> topRight.x >> topRight.y;
    cin >> bottomRight.x >> bottomRight.y;
    cin >> bottomLeft.x >> bottomLeft.y;

    //punti centrali dei lati
    point nord = {(topLeft.x + topRight.x) / 2.0, topLeft.y}; 
    point est = {topRight.x, (topRight.y + bottomRight.y) / 2.0};
    point sud = {(bottomLeft.x + bottomRight.x) / 2.0, bottomLeft.y};
    point ovest = {bottomLeft.x, (bottomLeft.y + topLeft.y) / 2.0};

    int N, K = 0;
    double X, Y;
    cin >> N;

    //raggi delle coppie di semicirconferenze
    double radx = abs(topRight.x - bottomLeft.x) / 2.0,
           rady = abs(topRight.y - bottomLeft.y) / 2.0;

    for (int i = 0; i < N; ++i)
    {
        cin >> X >> Y;
        int count =
            (hypot(nord.x - X, nord.y - Y) < radx) +
            (hypot(sud.x - X, sud.y - Y) < radx) +
            (hypot(ovest.x - X, ovest.y - Y) < rady) +
            (hypot(est.x - X, est.y - Y) < rady);
        //conto dentro quante circonferenze (da 1 a 3) il tulipano è compreso, per poi aggiornare K se il conteggio è uguale a 2
        K += (count == 2);
    }

    cout << K << endl;

    return 0;
}

Grazie mille in anticipo!

2

Non so se può essere utile ma ho avuto a che fare anche con gli angoli retti (o quasi).

1 Mi Piace
3

Stai attento quando fai i confronti tra numeri a virgola mobile, in quanto è facile che la perdita di precisione dia risultati inaspettati

4

ho considerato anche quel caso, infatti il punto posto su almeno una delle 4 circonferenze formerà angoli retti (per il teorema dell’angolo alla circonferenza) e non sarà quindi valido. per questo nella condizione di validità uso “<” e non “≤”.

allego un’immagine con le circonferenze per spiegare cosa intendo (con il primo caso di esempio)

Screenshot 2025-02-27 alle 10.13.27
Screenshot 2025-02-27 alle 10.13.271920×1048 78.3 KB

5

ho tolto i pow() e confronto la somma dei quadrati con il quadrato del raggio, ma l’ultimo testcase continua ad essere errato. c’è qualche altro modo per assicurarmi della precisione dei valori nel confronto?

6

Allora prova con questo esempio:
0 12
6 12
6 4
0 4
6
3 6
3 7
3 8
1 8
2 8
3 8

1 Mi Piace
7

In generale quando fai confronti tra numeri a virgola mobile devi tenere conto che è possibile avere problemi di precisione. Per questo motivo, confrontare due numeri a virgola mobile con gli operatori == > < può dare risultati inaspettati. Ad esempio, 0.1 + 0.2 == 0.3 potrebbe restituire false.

La soluzione è quindi verificare se la differenza tra i due numeri è inferiore a una soglia molto piccola (epsilon), che definisce il livello di precisione accettabile (più o meno piccola a seconda delle necessità). Ad esempio per confrontare due double potremmo fare qualcosa del genere:

#include <cmath>
#define EPSILON 1e-9

bool are_equal(double a, double b) {
    return std::fabs(a - b) < EPSILON;
}

In questo modo, i due numeri vengono considerati uguali se la loro differenza è trascurabile, evitando problemi legati all’approssimazione.
Prova a riguardare il tuo codice e capire come applicare quanto spiegato per evitare errori di approssimazione.

1 Mi Piace
8

il codice ritorna 3, ma visualizzandolo penso debba portare 1

9

Esatto.