http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1311. 可见区域(钟沛林)
时间限制:1.0s   内存限制:256.0MB  
总提交次数:   AC次数:   平均分:
将本题分享到:
   
 
  
问题描述
  在平面直角坐标系中有n条互不相交(没有公共点)且所在直线不会经过(0,0)的线段。有一个人站在(0,0),他的视野是360度的。但是他在某一个方向上的视野会被该方向上碰到的第一条线段所阻挡,问他能看到的区域面积有多大(数据保证是有限面积)。如下图(样例),可以看到的面积就是11。


  为了加大难度,他想知道,在删除一条线段的情况下能看到最大多大的面积(不保证是有限面积)。
  进一步,他还想知道,在删除两条线段的情况下能看到最大多大的面积(不保证是有限面积)。
输入格式
  第一行一个整数n表示线段条数。
  接下来n行,每行四个整数x1,y1,x2,y2表示一条线段两个端点的坐标。
输出格式
  第一行一个保留两位小数的实数,表示可见区域的面积。
  第二行两种可能,如果删除一条线段以后能使得看到的区域有无限大输出”infinite”,否则输出一个保留两位小数的实数,表示这种情况下能看到的最大面积。
  第三行两种可能,如果删除两条线段以后能使得看到的区域有无限大输出”infinite”,否则输出一个保留两位小数的实数,表示这种情况下能看到的最大面积。
样例输入
6
-1 -1 0 -1
0 -2 1 -1
-1 1 0 2
0 1 1 1
2 -2 2 2
-2 -2 -2 2
样例输出
11.00
infinite
infinite
数据规模和约定
  对于所有数据
  1<=n<=50000
  坐标的绝对值<=103

area1.in
4
-1 2 4 2
2 1 2 -4
1 -2 -4 -2
-2 -1 -2 4
area2.in
8
-1 2 4 2
2 1 2 -4
1 -2 -4 -2
-2 -1 -2 4
-3 6 12 6
6 3 6 -12
3 -6 -12 -6
-6 -3 -6 12
area3.in
12
-1 2 4 2
2 1 2 -4
1 -2 -4 -2
-2 -1 -2 4
-3 6 12 6
6 3 6 -12
3 -6 -12 -6
-6 -3 -6 12
-9 18 36 18
18 9 18 -36
9 -18 -36 -18
-18 -9 -18 36
area4.in
n<=10,坐标的绝对值<=10。
删除某条线段后可看到无限区域
area5.in
n<=1000
删除某条线段后可看到无限区域
area6.in
n<=1000
删除某条线段后可看到无限区域
area7.in
n<=50000
删除某条线段后可看到无限区域
area8.in
n<=50000
删除某条线段后可看到无限区域
area9.in
n<=50000
删除某条线段后可看到无限区域
area10.in
n<=50000
删除某条线段后可看到无限区域
area11.in
n<=200
删除两条线段后能看到无限区域
area12.in
n<=1000
删除两条线段后能看到无限区域
area13.in
n<=1000
删除两条线段后能看到无限区域
area14.in
n<=50000
删除两条线段后能看到无限区域
area15.in
n<=50000
删除两条线段后能看到无限区域
area16.in
n<=50

area17.in
n<=300

area18.in
n<=50000

area19.in
n<=50000

area20.in
n<=50000