注册
登录
论坛
搜索
帮助
导航
私人消息 (0)
公共消息 (0)
系统消息 (0)
好友消息 (0)
帖子消息 (0)
浆糊论坛-RO小站
»
一起来浆糊
» 一道C/C++/P语言题请各位帮忙
返回列表
发帖
WWWMXD
发短消息
加为好友
WWWMXD
(Broken sky)
巴西//罚
浆糊会员
UID
425421
帖子
404
精华
0
威望
20
阅读权限
100
注册时间
2007-5-26
1
#
跳转到
»
倒序看帖
打印
字体大小:
t
T
发表于 2008-12-26 22:03
|
只看该作者
一道C/C++/P语言题请各位帮忙
永别了,网络游戏
时间限制: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点共线
[
本帖最后由 WWWMXD 于 2008-12-26 22:29 编辑
]
收藏
分享
0
0
0
顶
踩
icysonyk
发短消息
加为好友
icysonyk
浆糊会员
UID
414377
帖子
1673
精华
0
威望
9
阅读权限
100
性别
男
注册时间
2007-3-20
2
#
发表于 2008-12-26 22:09
|
只看该作者
………………C不C无所谓的,这是算法题
ACM题吧……
再续RO之缘 ro.ragnarokonline.cn
纯粹给大家一个回忆的地方
TOP
WWWMXD
发短消息
加为好友
WWWMXD
(Broken sky)
巴西//罚
浆糊会员
UID
425421
帖子
404
精华
0
威望
20
阅读权限
100
注册时间
2007-5-26
3
#
发表于 2008-12-26 22:30
|
只看该作者
我一直做不出来,实在没办法了,只好上论坛找人帮忙了.
TOP
返回列表
[收藏此主题]
[关注此主题的新回复]
[通过 QQ、MSN 分享给朋友]