K - Polygon

Time limit: 2 s
Memory limit: 256 MiB
Languages: C, C++, Java, Python, ... (details)

As you all must know, ICPC is one of the most prestigious competitions in the field of computer science. This year, team Limscape is one of the strongest teams in the Caribbean Region, and they are training harder in order to advance to the 2020 ICPC World Finals. They recently took part in the Caribbean Local Contest and they could not solve only one problem, so they ended up tied in number of solved problems with teams UZ**, Frickyfox and VLCU.h. Now they want to solve it off-contest, and they ask for your help, due to your knowledge in Competitive Programming field. The problem was the following:

You are given a simple polygon (it doesn't intersect or touch with itself) consisting of $n$ vertices. A triangulation of this polygon is a subdivision in $n-2$ triangles, defined by a set of non-intersecting diagonals, in which the vertices of the triangles are also vertices of the polygon. Each vertex $i$ has a special value $v_{i}$ associated. We define the cost of a triangle as the bitwise XOR operation of the special values of vertices that form the triangle, and the cost of a triangulation as the sum of the costs of the triangles that compose it. We are interested in calculating the minimum possible value of a triangulation for such polygon.


The input consist of a line containing the integer $n$, the number of vertices that compose the given polygon $( 3 \leq n \leq 300 )$. The following $n$ lines contains $2$ space separated integers $x_i$ and $y_i$, describing the coordinates of the vertices in counterclockwise order $( -1000 \leq x_i, y_i \leq 1000 )$. Finally follows a line with $n$ space separated integers $v_i$, the special value for each vertex, in the same order as they are given in the input $( 0 \leq v_i < 2^{10} )$.


You should print a single line with the minimum cost of a triangulation for the given polygon.

Sample test(s)

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