P3875 [TJOI2010] Polluted Rivers

There is a city with many artificial rivers, each flowing either horizontally or vertically. For residents’ convenience, the rivers are arranged in a grid. The distance between adjacent rivers in both the horizontal and vertical directions is $1$ kilometer. The rivers enclose many cells, each of which is a community. Residents of a community can fetch water at any of the four river segments surrounding the community.

Unfortunately, not long after, some unscrupulous business owners built factories and polluted the rivers. Many residents living by the rivers drank polluted water and became ill. The government sent an investigator, Xiaoqiang (pinyin), to examine the pollution. The geography expert Xiaoqiang acted quickly and soon produced a pollution report. The report lists the polluted river segments. All residents who can fetch water from any such segment may get sick (the endpoints of a segment are ignored). However, Xiaoqiang could not figure out exactly how many communities’ residents would become ill, so he has asked for your help. 

The first line contains an integer $N$, the number of polluted river segments. Each of the next $N$ lines contains $4$ integers $x_1, y_1, x_2, y_2$, giving the start and end positions of a polluted segment. The two positions on each line are guaranteed to be distinct and satisfy $x_1 = x_2$ or $y_1 = y_2$.

Output a single integer $A$, indicating that there are $A$ communities whose residents will drink polluted water.

- For $10\%$ of the testdata, $1 \le x_1, y_1, x_2, y_2 \le 100$, $1 \le N \le 100$. - For $30\%$ of the testdata, $1 \le x_1, y_1, x_2, y_2 \le 10^4$, $1 \le N \le 100$. - For $100\%$ of the testdata, $1 \le x_1, y_1, x_2, y_2 \le 10^5$, $1 \le N \le 10^4$. Translated by ChatGPT 5