zadanie z spoj - Rysunki Bajtelka

Odpowiedz Nowy wątek
2019-08-09 21:00
0

Cześć, mam problem z zadaniem z spoja: link.
Napisałem taki program:

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct Point {
    int x, y;
};

long double calculateArea(const vector<Point>& vec)
{
    long double area = 0.0;
    for (int i = 0; i < vec.size()-1; i++) {
        if (i == vec.size()-2) {
            area += vec[i].x*vec[0].y - vec[i].y*vec[0].x;
        } else {
            area += vec[i].x*vec[i+1].y - vec[i].y*vec[i+1].x;
        }
    }
    return abs(area/2);
}

int main()
{
    int n;
    cin >> n;
    vector<Point> vec;  // tymczasowo przechowuje kazda z linii
    vector<long long int> results; // przechowuje wyniki obliczone z pary linii
    while (n--) {
        // pierwsza linia
        vec.clear();
        long long int ink = 0;
        Point p;
        cin >> p.x >> p.y;
        vec.push_back(p);
        do {
            cin >> p.x >> p.y;
            vec.push_back(p);
        } while (p.x != vec[0].x || p.y != vec[0].y);
        long double blackArea = calculateArea(vec);

        // druga linia
        vec.clear();
        cin >> p.x >> p.y;
        vec.push_back(p);
        do {
            cin >> p.x >> p.y;
            vec.push_back(p);
        } while (p.x != vec[0].x || p.y != vec[0].y);
        long double greyArea = calculateArea(vec);

        ink += blackArea < greyArea ? blackArea*10 : greyArea*10;
        ink += blackArea >= greyArea ? (blackArea-greyArea)*6 : (greyArea-blackArea)*6;
        results.push_back(ink);
        //getchar();
    }
    for (auto e : results) {
        cout << e << endl;
    }
    return 0;
}

dla testowych danych dostaje dwa błedne wyniki:
wejście:
18
5 4 3 8 9 2 2 5 -3 2 6 -4 3 -2 1 9 -9 -4 4 4 -4 3 -1 -5 -6 4 3 0 2 1 9 4 2 0 3 -4 5 4
9 3 0 4 -3 2 5 -6 3 -4 7 6 -3 2 7 -6 8 4 3 -6 9 4 -5 9 1 -1 9 4 7 2 -5 2 7 -8 -3 2 -2 1 0 4 0 5 6 -3 9 3
3634 346 35 346 34 346 34 634543 34634 346 43 346346 87 3 903463 34 34 34632 6346 25626 34578 7894 4326 4372 65357 23632 67432 76321 67622 356 3634 346
89540 34530 349 345 3045 4603 9343 -4563 -435 3423 2343 -3456 353 -3235 -8765 2345 -6322 225 -551525 3632 -62523 63252 -5526 65252 -63236 6332 89540 34530
89540 34530 349 345 3045 4603 9343 -4563 -435 3423 2343 -3456 353 -3235 -8765 2345 -6322 225 -551525 3632 -62523 63252 -5526 65252 -63236 6332 89540 34530
3634 346 35 346 34 346 34 634543 34634 346 43 346346 87 3 903463 34 34 34632 6346 25626 34578 7894 4326 4372 65357 23632 67432 76321 67622 356 3634 346
5 6 7 8 3 -5 2 -6 3 5 5 6
-5 -6 -7 -8 -3 5 -2 6 -3 -5 -5 -6
5 -3 1 4 -6 2 06 3 -2 9 5 -3
6 3 6 2 9 4 6 -2 7 -3 4 0 6 3
09 -05 3 9 04 5 03 5 014 4 5 2 345 23 2 -03 09 -05
9 4 -3 5 -3 43 -53 -3433 35 3 4 -5 -03 2 -2 -5 -4 2 -6 0 9 4
1 7 9 3 1 7
1 7 9 3 1 7
0 5 3 1 5 2 6 9 0 3 6 6 0 5
9 4 3 -7 -2 7 7 4 -6 -7 3 -2 -6 0 9 3 9 4
1 1 1 1
0 5 3 1 5 2 6 9 0 3 6 6 0 5
1 9 1 9
9 4 9 4
5 3 4 5 5 4 6 5 5 3
8 8 6 4 8 0 5 3 2 0 4 4 2 8 5 5 8 8
-1 1 0 0 1 1 0 -1 -1 1
-3 4 0 1 3 4 1 0 3 -4 0 -1 -3 -4 -1 0 -3 4
50000 30000 40000 50000 50000 40000 60000 50000 50000 30000
80000 80000 60000 40000 80000 0 50000 30000 20000 0 40000 40000 20000 80000 50000 50000 80000 80000
-10000 10000 0 0 10000 10000 0 -10000 -10000 10000
-30000 40000 0 10000 30000 40000 10000 0 30000 -40000 0 -10000 -30000 -40000 -10000 0 -30000 40000
8 8 6 4 8 0 5 3 2 0 4 4 2 8 5 5 8 8
5 3 4 5 5 4 6 5 5 3
-3 4 0 1 3 4 1 0 3 -4 0 -1 -3 -4 -1 0 -3 4
-1 1 0 0 1 1 0 -1 -1 1
1 2 2 1 2 2 1 2
0 2 3 0 2 3 0 2
2 3 5 2 3 3 5 4 2 3
1 5 1 3 5 0 3 2 5 1 6 2 4 3 6 3 6 4 7 4 7 1 6 1 6 0 8 0 8 5 1 5
wyjście:
1360
12404485333 -- źle
12404485333 -- źle
240
164
400136
0
512
147
0
88
88
8800000000
8800000000
88
88
23
139

Próbowałem inny algorytm do wyznaczania pola, ale to nie pomogło. Typy danych chyba są wystarczająco pojemne. Póki co nie mam pomysłu, gdzie może być błąd. Z góry dzięki za wszelkie wskazówki.

Pozostało 580 znaków

2019-08-10 09:37
0

Z tego co zrozumiałem to w zadaniu obszar blackArea musi być zawsze mniejszy od greyArea ("wszystkie składają się z dwóch obszarów, czarnego otoczonego w całości szarym").

long double trueGreyArea  = greyArea - blackArea;
ink = blackArea *10 + trueGreyArea *6;
edytowany 1x, ostatnio: TomaszLiMoon, 2019-08-10 10:00

Pozostało 580 znaków

2019-08-10 15:28
0
TomaszLiMoon napisał(a):

Z tego co zrozumiałem to w zadaniu obszar blackArea musi być zawsze mniejszy od greyArea ("wszystkie składają się z dwóch obszarów, czarnego otoczonego w całości szarym").

long double trueGreyArea  = greyArea - blackArea;
ink = blackArea *10 + trueGreyArea *6;

W tym przypadku problem jest taki, że najpierw przyjąłem wczytywanie obszaru czarnego, a potem szarego (tak jak jest w danych wejściowych na stronie zadania).
Z treści zadania nie wynika który obszar jest wczytywany jako pierwszy - i teraz widzę, że trzeba było jakoś inaczej nazwać pola obszarów (obecne trochę mylą, bo nie wiemy które tak naprawdę obliczamy, czarne ma być mniejsze, a szare większe i tyle?)

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0