2 shunfurh shunfurh 于 2017.01.17 13:33 提问

Paper Cut

Description

Still remember those games we played in our childhood? Folding and cutting paper must be among the most popular ones. Clever children will always search for something new, even when they play games like cutting paper. Now, Carol, a smart girl, asks her brother Mike to solve a puzzle. However, as always, Mike cannot find the solution, therefore he turns to you for help.

Carol's puzzle is simple to state. She folds the paper in a certain manner and then uses a knife to cut through the folded paper. What Mike needs to do is to tell how many pieces the folded paper will turn into after it is cut. To eliminate the ambiguity, we can coordinate the paper as [0, 1] * [0, 1], with the coordinates of lower left corner (0, 0). A fold is denoted by two points (x1, y1) and (x2, y2) on the folding line, with which, the direction of the line is determined by from (x1, y1) to (x2, y2). Carol will always fold the paper from left to right relative to the directed line given (see Figure-1). The cut is determined by the two points on the cut line. Please note that the points given to determine the fold or the cut are not necessarily on the paper.

Input

The first line of the input contains one integer t, the number of test cases. Then t cases follow. For each test case, the first line consists of an integer N (0 <= N <= 20), the number of folds, and the following N lines give two points on each fold line as x1, y1, x2, y2. The following line gives two points on the cut line in the same way.
Output

For each test case, output one line containing the number of pieces the paper will turn into after the cut.
Sample Input

2
1
0 0.5 1 1
0.5 0 0.5 1
1
0 0.5 1 1
0 0.4 1 0.4
Sample Output

2
3

1个回答

caozhy
caozhy   Ds   Rxr 2017.01.23 23:50
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
B. Cutting Codeforces Round #493 (Div. 2)
B. Cuttingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThere are a lot of things which could be cut — trees, paper, &quot;the rope&quot;. In this problem...
998B Cutting
B. Cuttingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThere are a lot of things which could be cut — trees, paper, &quot;the rope&quot;. In this problem...
Codeforces round 493 div2 B.Cutting (贪心技巧)
B. Cuttingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThere are a lot of things which could be cut — trees, paper, &quot;the rope&quot;. In this problem...
Codeforces Round #493 (Div. 2) B. Cutting
B. Cuttingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThere are a lot of things which could be cut — trees, paper, &quot;the rope&quot;. In this problem...
POJ2339 ZOJ1921 UVA10443 Rock, Scissors, Paper【Ad Hoc】
Rock, Scissors, PaperTime Limit: 5000MS Memory Limit: 65536KTotal Submissions: 4301 Accepted: 2490DescriptionBart's sister Lisa has created a new civilization on a two-dimensional grid. At the outset ...
Grabcut in one cut
原文地址:http://blog.csdn.net/wangyaninglm/article/details/50074613 One cut in grabcut(grabcut算法的非迭代实现?) 本文针对交互式图像分割中的图割算法,主要想翻译一篇英文文献。不足之处请大家指正。     这是博主近期看到的效果最好,实现最简单,运算时间最短的交互式图割算法,而且由于是发明图割算
normalized cut of image segmentation
normalized cut algorithms paper of PAMI
Cutting CodeForces - 998B (思维)
B. Cuttingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThere are a lot of things which could be cut — trees, paper, &quot;the rope&quot;. In this problem...
graph cut paper
this is graph cur algorithm paper
浅谈essay、paper和dissertation的区别
essay、paper和dissertation的区别 对于当代大学生来说,写论文时一件再平常不过的事了,在不短也不长的大学时光里,我们可能被要求要完成不少论文。那么,当老师布置下任务时,我们会发现任务的要求可能不仅仅包括essay、paper,还有dissertation 等等,那么,我们应该如何区别这三者的区别,这三者是否也有相同点呢。别急,接下来我们将会细细道来。 eaa