FR_07_12 - Czerwone mrówki

[pawelskakajacy]

Hej mecze sie z tym zadaniem juz drugi dzien i naprawde nie wiem co jest tutaj zle. Moze mi ktos pomoc?

    #include <iostream>
    #include <list>
    struct Ant
    {
            int x;
            int y;
            int c;
    };

    struct Area
    {
            int ax, ay;
            int bx;
            int cy;
    }; 

    bool belongs(const Area & area, const Ant & ant);

    int main()
    {
            Ant ant;
            Area area;
            std::list<Ant> blacks;
            unsigned long int d, n, count;
            std::cin >> d;
            std::cin >> n;
            for (int i = 0; i < d; ++i)
            {
                    area.ax = -1;
                    blacks.clear();
                    count = 0;
                    for (int j = 0; j < n; ++j)
                    {
                            std::cin >> ant.x;
                            std::cin >> ant.y; 
                            std::cin >> ant.c;
                            if (!ant.c)
                                    blacks.push_back(ant);
                            else if(!belongs(area, ant))
                            {
                                    ++count;
                                    if (area.ax == -1)
                                    {
                                            area.ax = ant.x;
                                            area.bx = ant.x;

                                            area.ay = ant.y;
                                            area.cy = ant.y;
                                            continue;
                                    }
                                    if (ant.x < area.ax)
                                            area.ax = ant.x;
                                    else
                                            area.bx = ant.x;
                                    if (ant.y < area.ay)
                                            area.ay = ant.y;
                                    else
                                            area.cy = ant.y;
                            }
                            else
                                    ++count;
                    }
                    for (auto &x : blacks)
                            if (belongs(area, x))
                                    ++count;
                    if (area.ax == area.bx || area.cy == area.ay)
                            std::cout << 0 << std::endl;
                    else
                            std::cout << count << std::endl;
            }
    }

    bool belongs(const Area & area, const Ant & ant)
    {
            if (ant.x >= area.ax && ant.y >= area.ay && ant.x <= area.bx && ant.y <= area.cy) 
                    return true;
            else
                    return false;
    }

[manjaro]

Ten test daje wynik 9 a powinno być 7
1
9
6 3 1
1 2 0
7 2 0
5 1 1
2 5 1
4 4 0
1 4 1
3 3 0
5 7 0

[pawelskakajacy]

OK Poprawilem linijki 51 do 59: https://ideone.com/3M0D2Y
ale dalej daje zla odp

[manjaro]

Jeszcze jest kwestia co będzie jeśli mrówki ustawią się w jednej linii.
Autor zadania tego nie sprecyzował, co na spoju jest dość powszechną praktyką, ale być może trzeba uwzględnić przypadek jeśli prostokąt zawęzi się do odcinka.
Z matematycznego punktu widzenia odcinek nie jest prostokątnym obszarem, ale te mrówki jakoś trzeba policzyć jeśli się ustawią w jednym rzędzie…
Tak sobie gdybam bo nie robiłem tego zadania, może ktoś kto już zaliczył się wypowie.

EDIT:
Niestety miałem rację. Trzeba uwzględnić sytuację kiedy mrówki stoją w szeregu.

[pawelskakajacy]

Uwzglednilem teraz ale dalej nie dziala ani kiedy uwzglednie tylko czerwone w szeregu, dam 0 dla szeregu, ani dla liczenia wszystkich mieszczacych sie w szeregu idk co mam zmienic w tym kodzie

[manjaro]

Kodu nie chce mi się analizować bo trochę długi i zagmatwany ja mam połowę krótszy ale podrzucę testy:
Input:
3
2
1 1 0
1 2 1
3
1 1 1
1 2 0
1 3 1
3
1 1 0
1 2 1
1 3 0

Output:
1
3
1

[pawelskakajacy]

Ok widze teraz ze zle wprowadzalem ilosc mrowek bo w moim programie byla ona taka sama dla wszystkich zdjec, w dodatku nwm czemu w strukturze area mialem smieci zamiast dobrych wspolrzednych od pierwszej czerwonej mrowki. Dzieki za pomoc, jeszcze mam pytanie jak mozna przyspieszyc ten program?

[manjaro]

Poczytaj o fast I/O w C++ to znacznie skróci czas. Na spoju to podstawa. Ale jeśli chcesz być lepszym programistą to raczej trzeba pisać bardziej optymalny algorytm. Tzn mniej pętli, mniej ifów itd…

[quenthui]

To nie jest dobre podejście.
Fast I/O ma sens w Javie albo Pythonie.
W C/C++ jeśli twoje rozwiązanie nie mieści się w wyznaczonym czasie, to znaczy, że masz za słaby algorytm.

@pawelskakajacy
dodaj na początku programu std::sync_with_stdio(0);
Czasem pomaga

[manjaro]

Ale jego program mieści się w czasie, problem w tym że jest dużo gorszy od innych pisanych w języku C++.