Решение задачи "Пара прямых" с 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;
}