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

View as PDF

Points: 15 (partial)
Time limit: 0.6s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You are listening to an interesting lecture about 1-String B2-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 points on the Cartesian plane. These will be your vertices, numbered from to . Then, you consider 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 and .
The next lines will have integer and pairs , the coordinates of each vertex in the graph in order from vertex to vertex . No two points will be at the same location. Additionally, no three points will be collinear.
The next lines will have and pairs , indicating that you should consider adding an edge from to .

#### Output Specification

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

#### Sample Input

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

#### Sample Output

3

#### Explanation of Output for Sample Input

The graph is a square, but the last edge 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 , and .

• commented on May 28, 2015, 2:24 p.m.

*Is the subtask weight assigned correctly? I mean 50% for n <= 20 and just 30% for n <= 300 ?

• commented on May 28, 2015, 3:30 p.m. edit 2

Fixed, thanks for noticing. I've updated the problem statement.

• commented on May 28, 2015, 1:28 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on May 28, 2015, 11:38 p.m. edited

That's just unfortunate.

• commented on May 28, 2015, 6:55 p.m.
• commented on May 30, 2015, 10:47 p.m.

• commented on May 28, 2015, 11:49 a.m.

Does segments intersect if they has infinitely many common points?

• commented on May 28, 2015, 11:57 a.m. edit 2

Sorry, consider that they DO intersect. I will verify the test data again.

• commented on May 28, 2015, 12:00 p.m.