Решение задачи "Пара прямых" с Codeforces

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


Задано n точек на плоскости, все точки имеют целочисленные координаты. Все точки различны.

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

Код

#include <bits/stdc++.h>

#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<int, int> 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;
}

         

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


Если точек меньше 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) коллинеарны.

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

Комментарии

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