Kingdom
题意翻译
平面有n个城市,初始时城市之间没有任何双向道路连接。你的任务是依次执行以下任务:
road A B:在城市A和城市B之间连接一条双向道路,保证这条道路不和其他道路在非端点处相交。
line C:询问一条y=C的水平线和多少个州相交,以及这些州一共包含几个城市。在任意时刻,每一组连接的城市形成一个州。在本指令中,C的小数部分保证为0.5.
例如,在图中,y=4.5穿过两个州,共八个城市;y=6.5穿过一个州,共5个城市。
**【输入格式】**
输入第一行为数据组T。每组数据第一行为一个整数n(1<=n<=100000)。以下n行每行两个整数x,y(0<=x,y<=1000000),即各城市坐标。城市编号为0~n-1。下一行为指令总数m(1<=m<=200000)。以下m行每行一条指令,其中A,B为不同的整数,且0<=A,B<n;C是小数部分保证为0.5的实数,且0<C<1000000。不会有两条道路连接一对相同的城市。每组数据至少有一条line指令。
**【输出格式】**
对于每条line指令,输出y=C穿过的州的数目和这些州包含的城市总数
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=447&page=show_problem&problem=4201
[PDF](https://uva.onlinejudge.org/external/14/p1455.pdf)