Solution Notes: There are several ways to approach this problem that lead to O(N) or O(N log N) solutions (O(N^2) isn't quite fast enough to solve all of the cases in time). To start with, there are really two interesting cases to check: either the points can all be covered by 3 horizontal lines, or by 2 horizontal lines and 1 vertical line. There are two other cases symmetric to these, but we can easily transform them into the two previous cases by swapping x and y for each point. In Richard's code below, he uses an STL map to store a "histogram" of how many times each distinct y coordinate appears, as well as the total number of distinct y coordinates. When a point is added to this data structure, its count is incremented (and if the count was previously zero, then we also increment the number of distinct y coordinates in total). When a point is removed from the data structure, its count is decremented (and if the count is now zero, we also decrement the total number of distinct y coordinates). Now to test if all our points can be covered with 3 horizontal lines, we add them all to our structure and check if the count of the total number of distinct y coordinates is at most 3. To test if 2 horizontal lines and 1 vertical line are sufficient, we sort the points on x, and for each distinct x coordinate, we temporarily remove all the points having that x coordinate and test if the number of distinct y coordinates drops to at most 2.

#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;

const int MAXN = 1001000;

pair<int,int> lis[MAXN];
map<int, int> cou;
int distinct;
int n;

void inc(int x) {
	if(cou[x] == 0) {
		distinct++;
	}
	cou[x] = cou[x] + 1;
}

void dec(int x) {
	cou[x] = cou[x] - 1;
	if(cou[x] == 0) {
		distinct--;
	}
}

int moo() {
	sort(lis, lis + n);
	distinct = 0;
	cou.clear();
	for(int i = 0; i < n; ++i) {
		inc(lis[i].second);
	}
	if(distinct <= 3) return 1;
	int i = 0, i1 = 0;
	while(i < n) {
		while(i1 < n && lis[i].first == lis[i1].first) {
			i1++;
		}
		for(int i2 = i; i2 < i1; ++i2) {
			dec(lis[i2].second);
		}
		if(distinct <= 2)  return 1;
		for(int i2 = i; i2 < i1; ++i2) {
			inc(lis[i2].second);
		}
		i = i1;
	}
	return 0;
}

int main() {
        freopen("3lines.in", "r", stdin);
        freopen("3lines.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 0; i < n; ++i) {
		scanf("%d%d", &lis[i].first, &lis[i].second);
	}
	if(moo()) {
		puts("1");
	}
	else {
		for(int i = 0; i < n; ++i) {
			swap(lis[i].first, lis[i].second);
		}
		if(moo()) {
			puts("1");
		}
		else {
			puts("0");
		}
	}
	return 0;
}