1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include <set>
#include <list>
#include <algorithm>

struct Car;
using car_it = std::set<Car>::const_iterator;

struct Car
{
    std::uint32_t pos;
    std::uint32_t time;
    mutable std::uint32_t collision_cout{0};
    mutable std::list<car_it> colliding_cars;

    friend bool operator<(const Car& a, const Car& b)
    {
        return a.pos < b.pos;
    }
};

int main(void)
{
    int n;
    int min_cars_to_remove = 0;
    std::multiset<Car> horizontal;
    std::multiset<Car> vertical;
    std::uint32_t type, pos, time;

    std::cin >> n;
    while(n--) {
        std::cin >> type >> pos >> time;
        if(type == 1) {
            horizontal.insert(Car{pos, time});
        } else {
            vertical.insert(Car{pos, time});
        }
    }

    // std::cout << "horizontal:\n";
    // for(const auto& car : horizontal) {
    //     std::cout << "(" << car.pos << "," << car.time << ") ";
    // }
    // std::cout << "\nvertical:\n";
    // for(const auto& car : vertical) {
    //     std::cout << "(" << car.pos << "," << car.time << ") ";
    // }
    // std::cout << "\n";

    for(auto hit = horizontal.begin(); hit != horizontal.end(); ++hit) {
        for(auto vit = vertical.begin(); vit != vertical.end(); ++vit) {
            if(vit->time + hit->pos == hit->time + vit->pos) {
                ++vit->collision_cout;
                vit->colliding_cars.push_back(hit);
                ++hit->collision_cout;
                hit->colliding_cars.push_back(vit);
            }
        }
    }

    std::list<car_it> all_cars;
    for (auto hit = horizontal.begin(); hit != horizontal.end(); ++hit) {
        all_cars.push_back(hit);
    }
    for (auto vit = vertical.begin(); vit != vertical.end(); ++vit) {
        all_cars.push_back(vit);
    }

    // all_cars.sort(
    //     [](const car_it& a, const car_it& b) { return a->collision_cout < b->collision_cout; });

    // std::sort(all_cars.begin(), all_cars.end(), [](const car_it& a, const car_it& b) {
    //     return a->collision_cout < b->collision_cout;
    // });

    auto max = std::max_element(all_cars.begin(), all_cars.end(), [](const car_it& a, const car_it& b) {
        return a->collision_cout < b->collision_cout;
    });

    while (max->_M_const_cast()->collision_cout != 0) {
        // remove the car with most collisions
        for (auto& car : max->_M_const_cast()->colliding_cars) {
            --car->collision_cout;
            // remove this car from all cars that have him on the list
            // for (auto it = car->colliding_cars.begin(); it != car->colliding_cars.end(); ++it) {
            //     if (*it == all_cars.back()) {
            //         car->colliding_cars.erase(it);
            //         break;
            //     }
            // }
        }

        ++min_cars_to_remove;
        all_cars.erase(max);
        // std::sort(all_cars.begin(), all_cars.end(), [](const car_it& a, const car_it& b) {
        //     return a->collision_cout < b->collision_cout;
        // });
        max = std::max_element(
            all_cars.begin(), all_cars.end(),
            [](const car_it& a, const car_it& b) { return a->collision_cout < b->collision_cout; });
        // all_cars.sort(
        //     [](const car_it& a, const car_it& b) { return a->collision_cout < b->collision_cout;
        //     });
    }

    // std::cout << "horizontal:\n";
    // for(const auto& car : horizontal) {
    //     std::cout << "(" << car.pos << "," << car.time << " c:" << car.collision_cout
    //               << ") collides with:\n";
    //     for(auto& col_car : car.colliding_cars) {
    //         std::cout << "    (" << col_car->pos << "," << col_car->time << ")\n";
    //     }
    // }
    // std::cout << "\nvertical:\n";
    // for(const auto& car : vertical) {
    //     std::cout << "(" << car.pos << "," << car.time << " c:" << car.collision_cout
    //               << ") collides with:\n";
    //     for (auto& col_car : car.colliding_cars) {
    //         std::cout << "    (" << col_car->pos << "," << col_car->time << ")\n";
    //     }
    // }

    // std::cout << "\n";

    std::cout << min_cars_to_remove << "\n";

    return 0;
}