F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 1357. -- [Baltic2009]Triangulation

1357: [Baltic2009]Triangulation

Time Limit: 20 Sec  Memory Limit: 64 MB
Submit: 51  Solved: 6
[Submit][Status][Discuss]

Description

多边形的三角剖分是指由这个多边形上的点组成的三角形的集合,这些三角形不能重叠,并且能 覆盖住整个多边形。对多边形的CUT指一条直线将多边形分成两部分。 现在给出一个多边形的三角剖分,每个三角形都有自己的颜色,问你对这个多边形最多可进行多少次CUT 使得同一颜色的点在同一块中.

Input

第一行给出数字n,3 ≤ n ≤ 100,000. 下面n-2行,每行四个数a,b,c,d表示由顶点a,b,c组成的三角形的颜色为d

Output

最多要进行多少次cut

Sample Input

input data1
5
1 2 3 2
4 5 1 1
3 1 4 2

input data2
6
1 4 2 1
2 4 5 2
6 2 5 3
3 6 5 1

Sample Output

output data1
1

output data2
0

HINT

Source

[Submit][Status][Discuss]

HOME Back