Construct an undirected graph where each vertex represents a moo particle and there exists an edge between two moo particles if they can interact. An interaction corresponds to removing a vertex with at least one adjacent edge.
Within each connected component, at least one particle must remain. Conversely, we can show that this is always attainable. Consider a spanning forest of the graph; just keep removing a particle that is a leaf in this forest.
It remains to show how to compute the number of connected components in faster than $O(N^2)$. Sort the moo particles in increasing order of $x$ and then $y$. Initially, suppose that each particle is its own connected component. Then while there exist two connected components that are adjacent in the order such that the minimum $y$-coordinate in the left component is at most the maximum $y$-coordinate of the right coordinate, combine them together.
For the following input (a combination of the two samples), the answer is 3.
7 1 0 0 1 -1 0 0 -1 3 -5 4 -4 2 -2
After this is done, the $i$-th moo particle in the sorted order is not in the same connected component as the $i+1$-st if and only if $\min(y_1,y_2,\ldots,y_i)>\max(y_{i+1},y_{i+2},\ldots,y_N)$ (which automatically implies that $\max(x_1,x_2,\ldots,x_i)<\min(x_{i+1},x_{i+2},\ldots,x_N)$). So after sorting we only need $O(N)$ additional time to compute the answer.
Dhruv Rohatgi's code:
#include <iostream> #include <algorithm> using namespace std; #define MAXN 100000 int N; int x[MAXN], y[MAXN]; int cid[MAXN]; int minl[MAXN]; int maxr[MAXN]; bool cmp(int a,int b) { if(x[a]==x[b]) return y[a]<y[b]; return x[a]<x[b]; } int main() { freopen("moop.in","r",stdin); freopen("moop.out","w",stdout); cin >> N; for(int i=0;i<N;i++) { cin >> x[i] >> y[i]; cid[i] = i; } sort(cid,cid+N,cmp); minl[0] = y[cid[0]]; for(int i=1;i<N;i++) minl[i] = min(minl[i-1], y[cid[i]]); maxr[N-1] = y[cid[N-1]]; for(int i=N-2;i>=0;i--) maxr[i] = max(maxr[i+1], y[cid[i]]); int ans = 1; for(int i=0;i<N-1;i++) if(minl[i] > maxr[i+1]) ans++; cout << ans << '\n'; }
Related (but harder) problems: