网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
Uyuw的音乐会
成绩 | 开启时间 | 2014年09月19日 星期五 10:08 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:08 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:08 |
输入文件 | concert.in | 输出文件 | concert.out |
【题目描述】
Remmarguts公主成功地解决了象棋问题。作为奖励,Uyuw计划举办一场音乐会,地点是以其伟大的设计师Ihsnayish命名的巨大广场。
这个位于自由三角洲联合王国(UDF,United Delta of Freedom)最繁华地带的广场是一个坐标范围[0,10000]*[0,10000]的正方形。有一些长椅已经固定在广场上许多年了,但是杂乱无章。见下图:
我们有三张长椅,并且观众面对的方向已经用箭头画出。这些椅子年代久远,并且沉重得无法移动。Remmarguts公主让广场现在的主人UW先生在广场上修建一个大的舞台。这个舞台应当尽可能大,但必须确保在任意长椅上任意位置的观众不必转身就能看到舞台(也就是说舞台必须在长椅所在直线的观众朝向那一侧)。
为了简化问题,舞台的高度可以任意高来确保只要你面向舞台所在的那一侧,你就能看到舞台上的歌唱家/画家——Uyuw,即使你的面前有数千张长椅。
作为一名脑残粉,你能告诉他们舞台的最大面积吗?
【输入格式】
输入包含不超过10组数据。
每组数据格式如下:
第一行有一个整数N(N<=20000),代表长椅的数量。
接下来有N行,每行有4个整数x1,y1,x2,y2,代表一张长椅。这张长椅是以(x1,y1)和(x2,y2)为端点的线段,并且面向其左侧。一个点(x,y)在线段左侧是指(x-x1)*(y-y2)-(x-x2)*(y-y1)>=0.
【输出格式】
对每组数据输出一个一个实数,即舞台的最大面积。精确到1位小数。你的答案被认为是正确的当且仅当它与标准答案之差小于0.2。
【样例输入】
3
10000 10000 0 5000
10000 5000 5000 10000
0 5000 5000 0
【样例输出】
54166666.7
【提示】
样例如下:
建议你采用Pascal中的Extended类型或者C/C++中的long double类型来避免精度误差。不过标程仅仅用了double。
【来源】
POJ 2451 By 朱泽园