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

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


Сезон охоты очень не долог, и поэтому оставшуюся часть года заядлые охотники развлекают себя тем, что стреляют по мишеням в тире. Тир представляет собой плоскость, на которой расставлены мишени. Размерами мишеней можно пренебречь и считать их точками с координатами (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/


Комментарии

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

  1. Avatar
    Тимур
    2021-12-14 17:23:05
    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
     
    int func(vector<double>arr) {
        sort(arr.begin(), arr.end());
        int k = 1, max=1;
        for (int i = 1; i < arr.size() ;i++)
        {
            if (arr[i]==arr[i-1])
            {
                k++;
            }
            else {
                k = 1;
            }
            if (k>max)
            {
                max = k;
            }
             
        }  
        return max;
    }
     
     
    int main() {
        int n,a1=0,a2=0,a3=0,a4=0;
        cin >> n;
     
        vector<double>arr1;
        vector<double>arr2;
        vector< double>arr3;
        vector< double>arr4;
     
        vector<double>res;
        for (int i = 0; i < n; i++)
        {
            double x, y;
            double k;
            cin >> x >> y;
            if (x > 0 && y > 0)
            {
                k = y / x ;
                arr1.push_back(k);
            }
            if (x < 0 && y > 0) {
                k = y / x ;
                arr2.push_back(k);
            }
            if (x < 0 && y < 0) {
     
                k = y / x ;
                arr3.push_back(k);
            }
            if (x > 0 && y < 0) {
                k = y / x ;
                arr4.push_back(k);
            }
     
            if (y == 0 && x > 0)
            {
                a1++;
            }
            if (y > 0 && x == 0)
            {
                a2++;
            }
            if (y == 0 && x < 0)
            {
                a3++;
            }
            if (y < 0 && x == 0)
            {
                a4++;
            }
        }
         
     
        res.push_back(func(arr1));
        res.push_back(func(arr2));
        res.push_back(func(arr3));
        res.push_back(func(arr4));
         
        res.push_back(a1);
        res.push_back(a2);
        res.push_back(a3);
        res.push_back(a4);
        int t = *max_element(res.begin(), res.end());
        if (t <= 0)
            cout << 0;
        else
            cout << t;
         
    }


Заявка на расчет