Решение задачи Охотник с Acmp

С пояснением   Просмотров: 68


Сезон охоты очень не долог, и поэтому оставшуюся часть года заядлые охотники развлекают себя тем, что стреляют по мишеням в тире. Тир представляет собой плоскость, на которой расставлены мишени. Размерами мишеней можно пренебречь и считать их точками с координатами (x, y). Также известно, что мишени сделаны из картона, поэтому за один выстрел можно поразить сразу все мишени, стоящие на линии выстрела. В начале координат стоит охотник и у него остался последний патрон. Охотник хочет использовать его эффективно – то есть за один выстрел поразить как можно больше целей. Помогите ему в этом.


Код

#include <bits/stdc++.h>

using namespace std;

int func(double x, double y, double x1, double y1)
{
    if(y * y1 >= 0 && x * x1 >= 0 && (x/x1 == y/y1 || (x == x1 && x == 0) || (y == y1 && y == 0)))
        return 1;
    return 0;
}
int main()
{
    int n, res = 1, k;
    cin >> n;
    vector<double> rx(n), ry(n);
    for(int i = 0; i < n; ++i){
        cin >> rx[i] >> ry[i];
    }

    while(rx.size() > 1){
        k = 1;
        for(int j = 1; j < rx.size(); ++j){
            if(func(rx[0], ry[0], rx[j], ry[j])){
                ++k;
                rx.erase(rx.begin() + j);
                ry.erase(ry.begin() + j);
                --j;
            }
        }
        rx.erase(rx.begin());
        ry.erase(ry.begin());
        if(k > res){
            res = k;
        }
    }
    cout << res;
    return 0;
}

         

Администратор Photo Автор: Администратор


Тест:
4
2 2
4 4
-2 -2
-4 -4
Ответ: 2

Коллинеарность векторов, условия коллинеарности векторов на сайте https://ru.onlinemschool.com/math/library/vector/colinearity/


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться