Как зайти в Даркнет?!
25th January, 01:11
4
0
Как в tkinter из поля ввода Entry получить значение в одну переменную и обновить строку кнопкой, затем получить ещё одно введённое значение и затем сложить их. Ниже пример кода
21st July, 19:00
891
0
Программа, которая создает фейковые сервера в поиске игровых серверов CS 1.6 Steam
21st March, 17:43
947
0
Очень долго работает Update запрос Oracle
27th January, 09:58
912
0
не могу запустить сервер на tomcat HTTP Status 404 – Not Found
21st January, 18:02
905
0
Где можно найти фрилансера для выполнения поступающих задач, на постоянной основе?
2nd December, 09:48
937
0
Разработка мобильной кроссплатформенной военной игры
16th July, 17:57
1724
0
период по дням
25th October, 10:44
3955
0
Пишу скрипты для BAS только на запросах
16th September, 02:42
3720
0
Некорректный скрипт для закрытия блока
14th April, 18:33
4613
0
прокидывать exception в блоках try-catch JAVA
11th March, 21:11
4380
0
Помогите пожалуйста решить задачи
24th November, 23:53
6084
0
Не понимаю почему не открывается детальное описание продукта
11th November, 11:51
4350
0
Нужно решить задачу по программированию на массивы
27th October, 18:01
4395
0
Метода Крамера С++
23rd October, 11:55
4308
0
помогите решить задачу на C++
22nd October, 17:31
4002
0
Помогите решить задачу на python с codeforces
22nd October, 11:11
4492
0
Python с нуля: полное руководство для начинающих
18th June, 13:58
2598
0
Решение задачи Пара прямых с Codeforces
С пояснением   Просмотров: 1016
Необходимо узнать, существуют ли две такие прямые, что каждая из заданных точек принадлежит хотя бы одной из них. Прямые могут совпадать.
Код
#include #define fore(i, l, r) for(int i = int(l); i < int(r); i++) #define all(a) (a).begin(), (a).end() #define sz(a) int(a.size()) #define mp make_pair #define x first #define y second using namespace std; typedef long long li; typedef pair pt; inline pt operator -(const pt &a, const pt &b) { return {a.x - b.x, a.y - b.y}; } inline li cross(const pt &a, const pt &b) { return a.x * 1ll * b.y - a.y * 1ll * b.x; } const int N = 200 * 1000 + 555; int n; pt p[N]; inline bool read() { if(!(cin >> n)) return false; fore(i, 0, n) scanf("%d%d", &p[i].x, &p[i].y); return true; } bool used[N]; bool check() { int i1 = -1, i2 = -1; fore(i, 0, n) { if(used[i]) continue; if(i1 == -1) i1 = i; else if(i2 == -1) i2 = i; } if(i2 == -1) return true; fore(i, 0, n) { if(used[i]) continue; if(cross(p[i2] - p[i1], p[i] - p[i1]) != 0) return false; } return true; } bool check2(pt a, pt b) { memset(used, 0, sizeof used); fore(i, 0, n) if(cross(b - a, p[i] - a) == 0) used[i] = 1; return check(); } inline void solve() { if(n <= 2) { puts("YES"); return; } if(check2(p[0], p[1]) || check2(p[0], p[2]) || check2(p[1], p[2])) puts("YES"); else puts("NO"); } int main(){ if(read()) { solve(); } return 0; }
 
 
 
 
 
Автор: Администратор
Автор: Администратор
Пояснение к задаче
Если точек меньше 3, то ответ YES. Иначе зафиксируем первые 3 точки. Проверим, правда ли 1-я и 2-я точки могут лежать на одной прямой. Для этого удалим все точки, которые попали на прямую, проходящую через точки 1 и 2, и проверим, правда ли оставшиеся точки лежат на одной прямой. Если нет, то аналогично проверим, правда ли, что точки 1 и 3 могут лежать на одной прямой. Если снова нет, то прямая, проходящая через точку 1, не может содержать точки 2 и 3, а, следовательно, 2 и 3 должны лежать на одной прямой. Если и сейчас не получилось разместить точки, то ответ NO.
Проверка, лежат ли точки a, b и c на одной прямой может быть сделана подсчетом псевдо-векторного произведения (b - a) × (c - a). Оно равно 0 когда вектора (b - a) и (c - a) коллинеарны.
Комментарии
или напишите нам прямо сейчас: