| 题目名称 | 1813. [国家集训队2012]可见区域 |
|---|---|
| 输入输出 | nt2012_area.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-11-12加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：4， 提交：38， 通过率：10.53% | ||||
 Wearry |
100 | 2.102 s | 3.16 MiB | C++ |
|
Wearry |
100 | 2.263 s | 3.61 MiB | C++ |
|
Wearry |
100 | 2.329 s | 3.61 MiB | C++ |
|
Wearry |
100 | 2.490 s | 3.38 MiB | C++ |
|
Wearry |
95 | 0.716 s | 3.61 MiB | C++ |
|
Wearry |
90 | 1.011 s | 2.93 MiB | C++ |
|
Wearry |
85 | 1.395 s | 3.16 MiB | C++ |
|
Wearry |
80 | 1.202 s | 3.83 MiB | C++ |
|
Wearry |
75 | 1.071 s | 2.70 MiB | C++ |
|
Wearry |
70 | 1.202 s | 3.16 MiB | C++ |
| 关于 可见区域 的近10条评论(全部评论) |
|---|
可见区域(钟沛林)
时间限制：1.0s 内存限制：256.0M
【问题描述】
在平面直角坐标系中有n条互不相交(没有公共点)且所在直线不会经过(0,0)的线段。有一个人站在(0,0)，他的视野是360度的。但是他在某一个方向上的视野会被该方向上碰到的第一条线段所阻挡，问他能看到的区域面积有多大（数据保证是有限面积）。如下图（样例），可以看到的面积就是11。
为了加大难度，他想知道，在删除一条线段的情况下能看到最大多大的面积（不保证是有限面积）。
进一步，他还想知道，在删除两条线段的情况下能看到最大多大的面积（不保证是有限面积）。
为了加大难度，他想知道，在删除一条线段的情况下能看到最大多大的面积（不保证是有限面积）。进一步，他还想知道，在删除两条线段的情况下能看到最大多大的面积（不保证是有限面积）。
【输入格式】
第一行一个整数n表示线段条数。
接下来n行，每行四个整数x1,y1,x2,y2表示一条线段两个端点的坐标。
接下来n行，每行四个整数x1,y1,x2,y2表示一条线段两个端点的坐标。
【输出格式】
第一行一个保留两位小数的实数，表示可见区域的面积。
第二行两种可能，如果删除一条线段以后能使得看到的区域有无限大输出”infinite”，否则输出一个保留两位小数的实数，表示这种情况下能看到的最大面积。
第三行两种可能，如果删除两条线段以后能使得看到的区域有无限大输出”infinite”，否则输出一个保留两位小数的实数，表示这种情况下能看到的最大面积。
第二行两种可能，如果删除一条线段以后能使得看到的区域有无限大输出”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
-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
infinite
infinite
【数据规模和约定】
对于所有数据
1<=n<=50000
坐标的绝对值<=103
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 |
|