Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.89/9: Рейтинг темы: голосов - 9, средняя оценка - 4.89
0 / 0 / 1
Регистрация: 18.02.2018
Сообщений: 112
1

Охотник acmp

21.06.2018, 09:29. Просмотров 1846. Ответов 8
Метки нет (Все метки)


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

Входные данные
В первой строке входного файла INPUT.TXT находится натуральное число N (N ≤ 100) – количество мишеней в тире. Далее следует N строк – описание мишеней. В (i+1)-й строке находится два целых числа x и y (-100 ≤ x, y ≤ 100) – координаты i-й мишени. Не существует двух мишеней, стоящих в одной точке, и никакая мишень не стоит в начале координат.

Выходные данные
В выходной файл OUTPUT.TXT выведите максимальное количество мишеней, которое может подстрелить охотник за один выстрел.

Я написал вот такую программу:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n,t=0;
    cin >> n;
    vector<pair<int, int> > a(n);
    for (int i = 0; i<n; i++) cin >> a[i].first >> a[i].second;
    int ma = 1;
    for (int i = 0; i<n; i++) {
        int l=0,g=1,g2=1;
        for (int j = i + 1; j < n; j++) {
            int x1 = a[i].first, y1 = a[i].second, x2 = a[j].first, y2 = a[j].second;
            if (y1 == y2) g++;
            else if (x1 == x2) g2++;
        }
        ma = max(max(ma, g), g2);
    }
    cout <<n-ma+1;
}
Моя программа не проходит 5 тест на сайте acmp. Помогите, пожалуйста, найти ошибку, или подскажите ,пожалуйста, как ее решать разумным способом.

Добавлено через 51 минуту
Ребят. Помогите, пожалуйста.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.06.2018, 09:29
Ответы с готовыми решениями:

№38 с acmp.ru
Решал так. Беру массив пар dp NxN, где номер строки - число цифр, убранных с правой стороны, а...

Графы (acmp 97)
В райской долине расположены N заповедников, имеющих форму прямоугольников. Однажды на собрании...

Задача 401 с acmp
Всем привет. Есть такая задача из категории &quot;Динамическое программирование&quot;. В динамике я всегда...

Степень строки(из acmp)
Привет всем. Я решаю такую задачу: Пусть задана строка s = s1s2...sn. Назовем ее k-ой (k &gt; 0)...

8
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
21.06.2018, 10:40 2
Нужно делать по-другому.
Например, построй вектор от двух точек (0, 0), (a[i].first, a[i].second)
А потом перебирай все остальные точки. Нужно, чтобы вектора ((0, 0), a[i]) и (a[i], a[j]) были коллинеарны
Конец.
0
0 / 0 / 1
Регистрация: 18.02.2018
Сообщений: 112
21.06.2018, 13:21  [ТС] 3
Что такое коллинеарны?
0
301 / 213 / 74
Регистрация: 23.05.2011
Сообщений: 970
21.06.2018, 13:25 4
Цитата Сообщение от msz301005 Посмотреть сообщение
Что такое коллинеарны?
Направлены в одну сторону. Геометрия, восьмой класс.
0
0 / 0 / 1
Регистрация: 18.02.2018
Сообщений: 112
22.06.2018, 08:55  [ТС] 5
А, понятно.

Добавлено через 24 секунды
А как это проверить?

Добавлено через 18 часов 2 минуты
Почитал про коллинеарность и написал вот такую программу:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int n,g,g2,g3;
typedef double d;
d kol(d x1,d y1,d x2,d y2,d x3,d y3){
    return ((x1*y2 + x2*y3 + x3*y1) - ( x2*y1 + x3*y2 + x1*y3))/2;
}
int main() {
    cin >> n;
    vector<pair<int, int> > a(n);
    for (int i = 0; i<n; i++) cin >> a[i].first >> a[i].second;
    int ans=0;
    for(int i = 0;i<n;i++){
        int g=1;
        for(int j = i+1;j<n;j++){
            if(!kol(0,0,a[i].first,a[i].second,a[j].first,a[j].second)){
                g++;
            }
        }
        ans=max(ans,g);
    }
    cout<<ans;
}
Сейчас я вроде бы всё правильно делаю, но у меня всё тот же 5 тест не проходит. Что я не так делаю?
0
Модератор
Эксперт по электронике
8356 / 6202 / 834
Регистрация: 14.02.2011
Сообщений: 21,552
22.06.2018, 09:07 6
мне кажется, тут нужно от декартовых координат перейти к полярным
https://ru.wikipedia.org/wiki/... _координат
а затем отсортировать по углу, и смотреть сколько мишеней с одним углом
0
301 / 213 / 74
Регистрация: 23.05.2011
Сообщений: 970
22.06.2018, 11:22 7
Да не надо никуда переходить.

Вот, тс, смотри решение задачи на python (на C++ писать было лень).
Попробуй напиши по такой же логике на C++.

Кликните здесь для просмотра всего текста

Python
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
n = int(input())
points = []
for i in range(n):
    x, y = map(int, input().split())
    points.append((x,y))
 
def is_coll(p1, p2):
    if p1[0]*p2[0]<0 or p1[1]*p2[1]<0:
        return False
    if p2[0]==0:
        return p1[0]==0
    if p2[1]==0:
        return p1[1]==0
    return p1[0]/p2[0]==p1[1]/p2[1]
 
checked = set()
max_shots = 0
i = 0
for point in points:
    i+=1
    if point in checked:
        continue
    checked.add(point)
    shots = 1
    for second_point in points[i:]:
        if is_coll(point, second_point):
            checked.add(second_point)
            shots+=1
    if max_shots<shots:
        max_shots=shots
 
print(max_shots)


Добавлено через 3 минуты

Не по теме:

Алсо, сайт acmp дебильный.
С какого рожна у них критерием качества кода является его объём?
Даже дебильные туториалы по ручной обфускации кода прямо на сайте.

0
Модератор
Эксперт по электронике
8356 / 6202 / 834
Регистрация: 14.02.2011
Сообщений: 21,552
22.06.2018, 11:44 8
Цитата Сообщение от New man Посмотреть сообщение
Да не надо никуда переходить.
а вот это что ты делаешь
Цитата Сообщение от New man Посмотреть сообщение
p1[0]/p2[0]==p1[1]/p2[1]
сравниваешь отношение, сиречь тангенс угла
если углы равны то и соотношения будут равны, этакий полупереход к полярным координатам только угол не высчитываешь
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
22.06.2018, 13:34 9
C++
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
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
int n,g,g2,g3;
typedef double d;
bool kol(d x1,d y1,d x2,d y2){
    return (x1*y2 == y1*x2);
}
 
int sign(int k) {
    if (k == 0) return 0;
    else if (k > 0) return 1;
    else return -1;
}
 
int main() {
    cin >> n;
    vector<pair<int, int> > a(n);
    for (int i = 0; i<n; i++) cin >> a[i].first >> a[i].second;
    int ans=0;
    for(int i = 0;i<n;i++){
        int g=1;
        for(int j = i+1;j<n;j++){
            if(kol(a[i].first,a[i].second,a[j].first,a[j].second) && sign(a[i].first) == sign(a[j].first) && sign(a[i].second) == sign(a[j].second)){
                g++;
            }
        }
        ans=max(ans,g);
    }
    cout<<ans;
}
Наслаждайся

Добавлено через 44 секунды
Цитата Сообщение от New man Посмотреть сообщение
С какого рожна у них критерием качества кода является его объём?
Ты совсем не шаришь.


Добавлено через 6 минут
Короче ссылку дать не могу (привет, параноидальная политика форума). Загугли "История одного байта". Это прекрасно
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.06.2018, 13:34

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

постройка дорог acmp
Привет всем. Решаю такую задачу: В известном городе Кызылорда, где находятся N центров, живет...

Боги (задача с acmp)
Здравствуйте. Проблема с решением задачи &quot;Боги&quot; (_http://********/?main=task&amp;id_task=93). Вот...

Количество палиндромов (задачка с acmp.ru)
Доброго времени суток. Нужна помощь с заданием на с++. Текст задания: Количество палиндромов...

Программа не проходит тест на acmp.ru
http://********/index.asp?main=task&amp;id_task=446 На хоккейном стадионе в одном большом городе...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.