Three lines (spring daily question 59)

Farmer John wants to monitor his with the new monitoring system he bought $N$ A cow .

The first $i$ The cow is in a position with integer coordinates $(x_i,y_i)$.

No two cows occupy the same position .

John's surveillance system contains three special cameras , Each camera can observe all the cows along a vertical or horizontal line .

Please confirm whether John can reasonably set the placement of the three cameras , So that he can monitor all $N$ A cow .

in other words , Please make sure that all... Can be placed through three vertical or horizontal lines $N$ The location of the cows is completely covered .

Input format
The first line contains integers $N$.

Next $N$ That's ok , Each line contains two integers $x_i,y_i$, The horizontal and vertical coordinates of the position of a cow .

Output format
If you can use three vertical or horizontal lines to place all $N$ The location of the cows is completely covered , Please export $1$, Otherwise output $0$.

Data range
$1\le N\le 50000,$
$0\le x_i,y_i\le 10^9$

sample input ：

6
1 7
0 0
1 2
2 0
1 4
3 4

sample output ：

1

Sample explanation
$y=0,x=1,y=4$ It can cover the positions of all cows .

#include<iostream>
#include<unordered_set>

#define x first
#define y second

using namespace std;

const int N = 50010;

typedef pair<int, int> PII;

int n;
PII q[N];
unordered_set<int> row, col;

int dfs(int u, int cnt){
    
    
    if(cnt > 3) return 0;
    if(u == n) return 1;
    
    if(row.count(q[u].x) || col.count(q[u].y)) 
        return dfs(u + 1, cnt);
    
    row.insert(q[u].x);
    if(dfs(u + 1, cnt + 1)) return 1;
    row.erase(q[u].x);
    
    col.insert(q[u].y);
    if(dfs(u + 1, cnt + 1)) return 1;
    col.erase(q[u].y);
    
    return 0;
}

int main(){
    
    
    scanf("%d", &n);
    
    for(int i = 0; i < n; i++)
        scanf("%d%d", &q[i].x, &q[i].y);
        
    printf("%d\n", dfs(0, 0));
    
    return 0;
}