DMPG '15 G2 - 1-String B2-VPG Representation of Planar Graphs

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 0.6s

Memory limit: 256M

Author:

FatalEagle

Problem types

You are listening to an interesting lecture about 1-String B₂-VPG Representation of Planar Graphs given by M. Derka, but as the presentation goes on and your understanding of the lecture lessens, your thoughts wander off into the realm of planar graphs…

You dream of a glorious planar graph. You wonder: what is the size of the maximum clique in this graph? A clique is a subgraph of the graph such that each pair of vertices in the clique are connected to each other by an edge. Specifically, a set of one single vertex is considered a clique. A maximum clique is a clique that has the most vertices out of all cliques in a graph.

Since you are skeptical that your graph is actually planar, you are determined to remove some edges such that it becomes planar. Therefore, your procedure of making the graph is as follows: first, you draw $N$ ~N~ points on the Cartesian plane. These will be your vertices, numbered from $1$ ~1~ to $N$ ~N~. Then, you consider $M$ ~M~ straight-line edges between the points in order. If adding an edge would make the graph non-planar (i.e. it intersects a previously added edge somewhere which is not the endpoints of the edge), you discard it. In particular, two lines that have infinitely many common points do intersect. Otherwise, you add it to the graph.

After making your graph in this fashion, you are too exhausted to complete your original goal by hand. Therefore, you decide to redo the whole procedure, but this time with a program you are about to write.

Input Specification

The first line of input will have two integers $N$ ~N~ and $M$ ~M~ $(0 \le M \le 5\,000)$ ~(0 \le M \le 5\,000)~.
The next $N$ ~N~ lines will have integer $x$ ~x~ and $y$ ~y~ pairs $(0 \le x, y \le 10\,000)$ ~(0 \le x, y \le 10\,000)~, the coordinates of each vertex in the graph in order from vertex $1$ ~1~ to vertex $N$ ~N~. No two points will be at the same location. Additionally, no three points will be collinear.
The next $M$ ~M~ lines will have $u$ ~u~ and $v$ ~v~ pairs $(1 \le u, v \le N, u \neq v)$ ~(1 \le u, v \le N, u \neq v)~, indicating that you should consider adding an edge from $u$ ~u~ to $v$ ~v~.

Constraints

Subtask 1 [30%]

$2 \le N \le 20$ ~2 \le N \le 20~

Subtask 2 [20%]

$2 \le N \le 40$ ~2 \le N \le 40~

Subtask 3 [50%]

$2 \le N \le 300$ ~2 \le N \le 300~

Output Specification

You should output the size of the maximum clique on one line.

Sample Input

Sample Output

Explanation of Output for Sample Input

The graph is a square, but the last edge $2 \leftrightarrow 4$ ~2 \leftrightarrow 4~ isn't in the graph as its presence would make the given embedding of the graph non-planar. There are two maximum cliques of size $3$ ~3~, $\{1, 2, 3\}$ ~\{1, 2, 3\}~ and $\{1, 3, 4\}$ ~\{1, 3, 4\}~.

Comments

-20

bossu commented on May 28, 2015, 5:28 p.m.

shit geometry problem why do retards think geometry is something good for contests?

This comment is hidden due to too much negative feedback. Show it anyway.

3

omaewamoushindeiru commented on May 29, 2015, 3:38 a.m. ← edited →

That's just unfortunate.

16

nullptr commented on May 28, 2015, 10:55 p.m. ← edited →

https://redmond.life/pages/realsalt

5

PaulOlteanu commented on May 31, 2015, 2:47 a.m.

I think he's already had his sodium intake for the day.