#P1117. 圆的交点

圆的交点

题目描述

现在给你一个二维平面。平面上有nn个圆,每个圆都有一条在xx轴上的直径(即关于xx轴对称)。现在,给你每个圆在xx轴上直径的两个端点(x1,0),(x2,0)(x_1,0),(x_2,0),你的任务是计数其中有多少对圆是有交点的。

提醒:是圆周相交,而不是面积相交。

输入格式

第一行一个正整数nn,表示一共有几个圆。

接下来nn行,每行两个正整数x1,x2x_1,x_2,以空格分开,表示一个以(x1,0),(x2,0)(x_1,0),(x_2,0)为直径两端点的圆。其中保证x1x2x_1 \neq x_2,但不保证x1<x2x_1<x_2

输出格式

一个整数,表示有多少对圆之间有交点。

4
1 4
1 2
2 3
4 3
4

样例解释

共有4对圆之间有交点。

数据规模与约定

每组数据点10分,共10组数据。对全体数据有直径端点坐标 (x,0)(x,0) 满足 0x1090 \leq x \leq 10^9

数据点编号 n的范围 其他说明
#1~#4 1n101\le n\le 10
#5~#6 1n1,0001\le n\le 1,000 所有圆直径都是1
#7~#10

大样例

大样例下载