Resources

Introduction

A planar graph is a set of vertices and edges that can be drawn such that no two edges cross each other. Often, it is possible to make a graph planar by redrawing the edges.

Given a planar graph, we can apply Euler's formula $V - E + F = 2$ to relate the number of vertices ($V$), edges ($E$), and faces ($F$) of the graph.

The equation is related to the theorem that for any convex polyhedron, $V - E + F = 2$ will hold true, since every convex polyhedron can be transformed into a planar graph.

This can be expanded to graphs that are not connected to incorporate connected components. To avoid overcounting the external face of the connected components, the equation subsequently becomes $V - E + F = C + 1$, where $C$ is the number of connected components.

Example - Build Gates

Explanation

We define the nodes as points with a fence, and edges as fence segments. Notice that because no two fence segments cross each other, the fence forms a planar graph in which every closed-off region, including the region outside the fences, counts as a face. Every time we combine two faces by adding a gate, the number of faces decreases by $1$. Thus, the answer is the number of faces in the graph minus one.

As a reminder, Euler's formula states that $F=E-V+2$, where the fences represent edges and the coordinates represent vertices. To count the edges, we only need to count the unique unit-length segments Farmer John places. Likewise, to count the vertices, we only need to count the unique positions Farmer John visits. Both counts can be obtained using sets.

Once we calculate these values, we can plug them back into the formula and obtain our answer.

Implementation

Time Complexity: $\mathcal{O}(N \log N)$

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {

	freopen("gates.in", "r", stdin);
	freopen("gates.out", "w", stdout);

	int n;
	cin >> n;

Problems