| 永别了，网络游戏 |
| 时间限制：1秒 内存限制：64M |
| 描述 Description 佳佳整天沉迷在网络游戏中，虚度青春。终于有一天，他意识到网络游戏对身心是有害的，他决定从此不玩网络游戏了。但是他很难克制自己玩游戏的念头。于是，他在晚上向着月亮祈祷：月亮姐姐，请你帮我戒除网络游戏吧！ 或许是佳佳人品好的原因，月亮姐姐出现在他的面前：我可以帮助你戒除，但是你必须通过我的考验。 在月亮上，月亮姐姐常和芙蓉哥哥玩这样一个游戏：月亮姐姐给出一个凸多边形，芙蓉哥哥会用一条直线把这个凸多边形分成两部分，如果这两部分面积之差不超过一个数delta，那么芙蓉哥哥就保留这个凸多边形，否则芙蓉哥哥会去除面积较小的一部分。 每次游戏前芙蓉哥哥会给出n条直线。问月亮姐姐应该以怎样的顺序用这n条直线割凸多边形，使得剩下的图形面积最大？ 注：若直线和凸多边形不相交，那么芙蓉哥哥会保留这个凸多边形。 现在月亮姐姐把这个问题交给了你，你有信心解决它吗？ 输入格式 Input Format 第一行输入一个正整数k，表示初始时多边形的顶点数。 以下k行按逆时针顺序给出多边形的顶点坐标Xi,Yi。 第k+2行输入一个正整数n，表示直线的数目。 以下n行，每行4个整数Xi1, Yi1, Xi2, Yi2，表示直线上的不重合两点的坐标。 最后一行输入一个小于10000的非负实数delta。 输入数据保证所有给出的坐标值都是绝对值不超过500的整数 对于10%的数据，n<=1； 对于70%的数据，n<=8； 对于100%的数据，n<=9，k<=20。 输出格式 Output Format 一个实数，表示最大可能得到的面积，保留5位小数。 样例输入 Sample Input 4 -100 -100 100 -100 100 100 -100 100 1 -1 0 1 0 0 样例输出 Sample Output 40000.00000 精度取1e-8足够 每组输入数据中的点保证无3点共线 |
| 欢迎光临 浆糊论坛-RO小站 (http://bbs.rohome.cn/) | Powered by Discuz! 7.2 |