0 / 0 / 0
Регистрация: 01.10.2020
Сообщений: 2
1

Убедиться, что можно проложить не более двух линий метро так, чтобы все станции лежали хотя бы на одной из линий

01.10.2020, 23:20. Показов 1207. Ответов 4

Студворк — интернет-сервис помощи студентам
Ограничение времени 1 секунда
Ограничение памяти 512Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
В одном из крупнейших городов Байтландии, Байтсбурге, ведётся строительство второй очереди метрополитена. Во время строительства первой очереди были построены
N
станций, не соединённых между собой. Согласно генеральному плану, метро в Байтсбурге должно состоять не более, чем из двух линий. Каждая линия метро представляет собой прямую.
Президент компании, отвечающей за прокладку линий, хочет убедиться, что можно проложить не более двух линий метро так, чтобы все построенные станции лежали хотя бы на одной из двух линий.

Формат ввода
Первая строка входа содержит одно целое число
N
— количество станций (1≤N≤105).
Каждая из последующих
N
строк содержит два целых числа xi и yi
, по модулю не превосходящие 109
— координаты очередной станции. Гарантируется, что никакие две станции не совпадают.

Формат вывода
Если можно проложить не более двух линий метро так, чтобы каждая из станций оказалась хотя бы на одной линии, выведите “yes”. Иначе выведите “no”.
Пример 1
Ввод Вывод
6
0 1
1 1
2 1
0 2
1 3
2 2
no
Пример 2
Ввод Вывод
6
2 2
4 6
1 0
2 1
6 1
1 1
yes
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.10.2020, 23:20
Ответы с готовыми решениями:

Соединить все города телефонной связью так, чтобы общая длина телефонных линий была минимальной
Дана плоская страна и в ней n городов. Нужно соединить все города телефонной связью так, чтобы...

Вывод на экран случайных эллипсов, линий, треугольников, прямоугольков, ромбов, линий, пикселей
вывод на экран случайных эллипсов, линий, треугольников, прямоугольков, ромбов, линий, пикселей и...

Приведите к каноническому виду уравнения линий второго порядка, установите тип этих линий и их расположение
приведите к каноническому виду уравнения линий второго порядка/ установите тип этих линий и их...

Сколькими способами он может выложить все эти шары в ряд так, чтобы никакие два черных шара не лежали рядом
У Сережи 9 белых и 7 черных шаров. Сколькими способами он может выложить все эти шары в ряд так,...

4
Вездепух
Эксперт CЭксперт С++
11087 / 6054 / 1652
Регистрация: 18.10.2014
Сообщений: 15,196
02.10.2020, 02:10 2
Цитата Сообщение от smallhacker Посмотреть сообщение
количество станций (1≤N≤105).
Цитата Сообщение от smallhacker Посмотреть сообщение
строк содержит два целых числа xi и yi, по модулю не превосходящие 109
105? 109? Что за странные ограничения?

Берем 4 произвольных точки из исходного набора:

* Если среди них есть хотя бы 3 коллинеарных точки, то они жестко определяют первую линию метрополитена. Все остальные точки либо принадлежат этой линии, либо определяют вторую линию метрополитена. Проверяем остальные точки.

* Если среди них нет 3-х коллинеарных точек, то они определяют три возможных конфигурации двух линий метрополитена. Проверяем остальные точки на предмет соответствия этим конфигурациям.
2
3 / 3 / 0
Регистрация: 05.06.2019
Сообщений: 82
16.12.2020, 17:56 3
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
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
129
130
131
132
133
134
135
136
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
 
 
struct line {
    int k, b;
    bool x = false;
    long long c = 0;
};
 
int n;
vector<line> lines;
vector<pair<int, int>> p;
 
bool Is3PointsOnLine(pair<float, float> p1, pair<float, float> p2, pair<float, float> p3) {
    if ((p2.first - p1.first) != 0 && (p2.second - p1.second) != 0) {
        return ((p3.first - p1.first) / (p2.first - p1.first) == (p3.second - p1.second) / (p2.second - p1.second));
    }
    else {
        //прямая вида x = a
        if ((p2.first == p1.first && p2.second == p1.second) || (p2.first == p1.first && p2.first == p3.first) || (p2.second == p1.second && p2.second == p3.second))
            return true; //fix me
        else
            return false;
    }
}
 
//лежит ли точка на прямой
bool PointIsOnLine(line l, int x, int y) {
    if (!l.x) {
        if (y == ((l.k * x) + l.b))
            return true;
    }
    else {
        if (x == l.b)
            return true;
    }
    return false;
}
 
//составляем уравнение прямой
line f(pair<int, int> c1, pair<int, int> c2) {
    int x1 = c1.first;
    int y1 = c1.second;
    int x2 = c2.first;
    int y2 = c2.second;
 
    line ans;
    if (x2 != x1) {
        ans.k = (y2 - y1) / (x2 - x1);//fix
        ans.b = -(x1 * y2 - x1 * y1 - x2 * y1 + x1 * y1) / (x2 - x1);
        ans.x = false;
        ans.c = 0;
    }
    else {
        ans.k = 0;      
        ans.b = x1;
        ans.x = true;
        ans.c = 0;
    }
 
    return ans;
}
 
int a() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (j != i) {
                for (int k = 0; k < n; k++) {
                    if ((k != i) && (k != j) && (Is3PointsOnLine(p[i], p[j], p[k]))) {
                        lines.push_back(f(p[i], p[j]));
                        return 0;
                    }
                }
            }
        }
    }
}
 
int main() {    
    cin >> n;
    p.resize(n);
 
    vector<int> not_used;
 
    for (int i = 0; i < n; i++)
        cin >> p[i].first >> p[i].second;
    
    if (n < 5) {
        cout << "yes";
        return 0;
    }
    else {
        //ищем первую прямую
        a();
 
        if (lines.size() == 0) {
            cout << "no";
            return 0;
        }
 
        pair<int, int> e = { -8,-8 };               
 
        for (int i = 0; i < n; i++) {
            if (PointIsOnLine(lines[0], p[i].first, p[i].second)) {
                lines[0].c++;
            }
            else if (e.first == -8) {
                e.first = i;
            }
            else if (e.second == -8) {
                e.second = i;
                lines.push_back(f(p[e.first], p[e.second]));
                lines[1].c = 2;
                e = { -5,-5 };
            }
            else if (PointIsOnLine(lines[1], p[i].first, p[i].second)) {
                lines[1].c++;
            }
            else {
                cout << "no";
                return 0;
            }
        }   
        
        
        cout << "yes";
        return 0;       
    }   
 
    return 0;
}
Почему этот код выдает WA на 7 тесте? Что я не учел?
0
Вездепух
Эксперт CЭксперт С++
11087 / 6054 / 1652
Регистрация: 18.10.2014
Сообщений: 15,196
17.12.2020, 06:19 4
Цитата Сообщение от sadfasfsad Посмотреть сообщение
Почему этот код выдает WA на 7 тесте?
Что это за набор букв? Что такое "WA"? Что такое "7 тесте"?

Цитата Сообщение от sadfasfsad Посмотреть сообщение
C++
1
bool Is3PointsOnLine(pair<float, float> p1, pair<float, float> p2, pair<float, float> p3) {
Откуда вдруг ни с того ни с сего взялся <float, float>?

Вся функция содержит неоправданные сравнения плавающих значений на равенство.

Цитата Сообщение от sadfasfsad Посмотреть сообщение
C++
1
2
3
4
5
6
struct line {
    int k, b;
...
        ans.k = (y2 - y1) / (x2 - x1);//fix
        ans.b = -(x1 * y2 - x1 * y1 - x2 * y1 + x1 * y1) / (x2 - x1);
...
... и при этом коэффициенты уравнения прямой - целые числа??? Как это вообще могло работать на любом тесте?
0
Yetty
17.12.2020, 06:35     Убедиться, что можно проложить не более двух линий метро так, чтобы все станции лежали хотя бы на одной из линий
  #5

Не по теме:

Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Что такое "WA"?
WA (wrong answer) - неправильный ответ
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Что такое "7 тесте"?
при тестировании на 7 тесте WA

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.12.2020, 06:35

Сколькими способами можно разложить 20 одинаковых предметов по 5 различимым ящикам так, чтобы а) оказалось не более двух пустых ящиков; б) в каждом ящ
Сколькими способами можно разложить 20 одинаковых предметов по 5 различимым ящикам так, чтобы а)...

Каким числом способов можно выбрать 5 карт так, чтобы среди них оказались все карты одной масти?
Доброго времени суток!Помогите решть задачу, а то я дуб-дубом в комбинаторике. Условие: Имеется...

Добрый день, где можно найти или скачать перечень станции метро?
Добрый день, гдеможно найти или скачать перечень станции метро Москви и Санкто петербурга?

Непрорисовка двух линий
Добрый день! Использую OpenGL ES 1.1 на iOS 7.1. Создаю обычный FBO на весь экран (1024*768) и...

Пересечение двух линий
figure; plot(X,Y1) hold on; plot(X,Y2) меня интерисует точка пересичения Y1 и Y2 (её x,y ).

Пересечение двух линий
Как узнать в какой кочке(пиксиле) пересекаютса две прямие


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru