| 题目名称 | 1692. Uyuw的音乐会 |
|---|---|
| 输入输出 | concert.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 6000 ms (6 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-08-31加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：57， 提交：154， 通过率：37.01% | ||||
 Foenix |
100 | 0.261 s | 1.66 MiB | C++ |
 gls1196 |
100 | 0.310 s | 2.15 MiB | C++ |
 thomount |
100 | 0.372 s | 6.01 MiB | C++ |
 mikumikumi |
100 | 0.398 s | 1.08 MiB | C++ |
|
mikumikumi |
100 | 0.399 s | 1.08 MiB | C++ |
 ztx |
100 | 0.414 s | 0.29 MiB | C++ |
|
gls1196 |
100 | 0.418 s | 2.15 MiB | C++ |
 L_in |
100 | 0.440 s | 2.46 MiB | C++ |
|
Foenix |
100 | 0.443 s | 1.84 MiB | C++ |
 天一阁 |
100 | 0.471 s | 0.77 MiB | C++ |
| 关于 Uyuw的音乐会 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
| ||||
|
计算几何的知识遗忘的好快啊
半平面交都不会写了  Go灬Fire
2017-03-17 20:51
7楼
| ||||
|
可怕，发现之前的模板是错的- -
| ||||
|
再次被读入坑。。。。。。
| ||||
|
这题艹的窝也真是酸爽
| ||||
|
我就不信这组数据是 0.6 ,我可是用几何画板画的
 8 9 3 0 6 5 8 3 4 5 1 1 10 4 3 5 7 9 2 0 6 4 5 2 5 1 6 2 5 4 6 4 7 | ||||
|
这题有问题吧
1.同楼上 2.我用simpson故意少积掉F(x)为负数之中的F(x)为正数区域才过了。 cheat了，求不喷~~~~(>_<)~~~~ 脑残+手抖，交了好多次求不喷。。。。。 | ||||
|
半平面交模板题
| ||||
ONCE AGAIN
FoolMike
Satoshi
new ioer
cstdio【题目描述】
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 朱泽园