Problem 1108. -- 菜哭武的狗子们

1108: 菜哭武的狗子们

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 185  Solved: 20
[Submit][Status][Web Board]

Description

新格尔公司的天才程序员菜哭武特别喜欢猫,他给他养的每一只猫都取名为“狗子”。但是“狗子”们实在是太调皮了,于是菜哭武买了三个摄像头时刻监视它们。假设“狗子”们的坐标是固定的,他想知道这三个摄像头能否通过合理的摆放,来观察到所有的“狗子”。
每个摄像头的可见范围只有水平或者垂直于坐标系的一条直线。

Input

题目包含多组数据。
输入的第一行有一个整数T(1 <= T <= 5)。
对于每组数据分为N+1行:
第一行,一个正整数N。代表“狗子”的数量。1 <= N <= 100,000。
第二行至N+1行,每行两个整数Xi,Yi代表第i只“狗子”的坐标,不会出现相同的坐标,0 <= Xi <= Yi <= 1,000,000,000 。

Output

对于每组数据,输出的第一行为Case #x:,其中x是数据编号(从1开始),
第二行是一个整数1或者0,1代表小王能够通过三个摄像头观察到所有的“狗子”;0则代表不能。

Sample Input

1
5
2 0
1 5
3 1
0 0
3 11

Sample Output

Case #1:
1

HINT

在 y = 0、x = 3、x = 1处设置摄像头,可以观测到所有的“狗子”。

Source

[Submit][Status]