切换到宽版
  • 36600阅读
  • 59回复

[待解决] [+500威望+500财富+提升为荣誉会员] 凸多边形(polygon) [复制链接]

上一主题 下一主题
离线archimedes
 

只看楼主 倒序阅读 0 发表于: 2006-02-26
— 本帖被 archimedes 执行加亮操作(2007-07-26) —
凸多边形(polygon)
[[此题是NOI2006重庆赛区选拔赛题目 我参加了,但是没有进入NOI,因为分数不够]]
[悬赏 +500财富 +500威望 提升为荣誉会员]
逆时针给出n个凸多边形的顶点坐标,求他们交的面积。例如n=2时,两个凸多边形如下图:

则相交面积为5.233。
[输入]
polygon.in第一行有一个整数n表示多边形的个数,以下依次描述各个多边形。第i个多边形的第一行包含一整数mi,表示多边形的边数,以下mi行每行两个整数,逆时针各出各个顶点的坐标。
[输出]
polygon.out仅包含一个实数,表示相交部分的面积,保留三位小数。
[样例输入]polygon.in
2
6
-2 0
-1 2
1 -2
2 0
1 2
4
0 -3
1 -1
2 2
-1 0
[样例输出]polygon.out
5.233
[限制]
50%的数据满足n=2
100%的数据满足2<=n<=10, 3<=mi<=50,每位坐标为[-1000,1000]内的整数。
离线stevenjl

只看该作者 1 发表于: 2006-05-19
I get no answer
Dream Walker...
离线阿瞬
只看该作者 2 发表于: 2006-05-31
好难啊!!!!!!!!1
离线archimedes

只看该作者 3 发表于: 2006-07-09
No one can solve this???
离线勇气les
只看该作者 4 发表于: 2006-07-20
先算两个,合并成一个
算的时候,一个为基础,一个将它的线段分成“里面”,“外面”(出现一个交点,这条线段从
“里面”到“外面”或从“外面”变成了“里面”)
于是,交点就求出来了,然后,再找一个东西,在合并
直到只有一个东西了
离线cefly
只看该作者 5 发表于: 2006-07-30
汗。。好久问一下我们数学老师多。。。。
离线r134a
只看该作者 6 发表于: 2006-07-30
二维凸包,好象不是~~~
微积分????

网上有解题报告没?~~~
.


祝大家明年NOIP大获全盛!


.
离线swj05652
只看该作者 7 发表于: 2006-08-30
可以用蒙特卡洛方法:就是随机选择一些实数点,判断每一个点是否在所有多边形内。利用概率得出近似结果。
判断一点是否在一个凸多边形内的方法是:从这个点引一条任意方向的射线,看它与多边形的交点有几个,如有1个便是在形内,否则在形外;为了防止射线穿过顶点时的特殊情况,随机多选择几条射线来看就可以了。(即要求每一条线都只有一个交点)。
这题的数据要求大约需要选取x的范围*y的范围*1000*5 个点,所以只能对付小一点的数据。
离线swj05652
只看该作者 8 发表于: 2006-08-30
还有7楼说的方法只适用于整点多边形,否则也算不出5.233这样的结果
离线archimedes

只看该作者 9 发表于: 2007-07-09
NOBODY IN THIS FORUM CAN SOLVE THIS?????
I HAVE BEEN WAITING FOR AN ANSWER SINCE FEBUARY 2006!!!

I'M REALLY DISAPPOINTED!
快速回复
限100 字节
 
上一个 下一个