Posted on 2006-12-07 14:42
TPC2005 阅读(512)
评论(1) 编辑 收藏 引用 所属分类:
UVA 题目讨论
题目链接:http://acm.uva.es/p/v1/109.html
一道综合性的几何题,题目看上去比较难,因而提交量也较其它题目少.
题目大意如下:
在500×500大小的虚拟空间中,存在N个王国,每个王国由一个电站和M个居民组成.王国的范围是一个包含其全部居民和电站的最小凸多边形.
然后给出至少一个导弹着陆的位置,凡是导弹着陆点位于某个王国的范围,则这个王国的电站被破坏,不杀伤居民.
求最后剩下的电站被破坏的王国的总面积.
输入一个整数M,接下来有M组数据,第一个是该王国电站的x,y坐标(坐标均为整数,范围[0,500]).然后是M-1组居民坐标.
有若干个王国的数据,重复以上,-1代表结束输入.然后有若干个导弹的坐标(x,y).
王国数量不超过20,每个王国的坐标(居民数加一个电站)不超过100,导弹数不超过100.
输出只有一个,总面积为浮点数,保留两位小数,(事实上,结果小数位一定为x.50或x.00)
提供一个求多边形面积的公式:这里(x1,y1)~(xn,yn)为多边形顶点坐标,x0=xn,y0=yn
如果多边形顶点顺序为逆时针,则结果为正,反之结果为负.
即a=abs(x0y1-x1y0+x1y2-x2y1+......+xn-1yn-xnyn-1)/2
这个公式是由,求多边形向量的叉积演变过来的.详细推导过程
既然求多边形面积有公式可参考,那么题目的难点就在于:
已知若干个点,求能够包含全部点的凸多边形.(一定为凸多边形,否则你试试怎么确定唯一)
这里还有一个公式:对于向量(x1,y1)->(x2,y2),判断点(x3,y3)在向量的左边,右边,还是线上.
p=x1(y3-y2)+x2(y1-y3)+x3(y2-y1).
p<0 左侧
p=0 线上
p>0 右侧
然后,卷包裹大法,^_^
找到最外面的一个点,比如最底下(y最小)的一个点.
然后比较各点,找出具有最大夹角的那个点,最后回到出发点.
注意特殊情况,三点共线.
当然还有很多求凸包的算法,详见<算法艺术与信息学竞赛>一书.[p391]
附上代码:
源代码下载
1
/**/
/*
***********************************
*/
2
/**/
/*
Pro_109 SCUD Busters
*/
3
/**/
/*
CPU Time 0:00.002 Memory Minimum
*/
4
/**/
/*
Ranklist 147 Programmed By Wingy
*/
5
/**/
/*
***********************************
*/
6
7
#include
<
stdio.h
>
8
#define
MAX_KINGDOMS 20
//
最大王国数量
9
#define
MAX_INDICATES 100
//
单个王国最多地点数
10
#define
MAX_SCUD 100
//
最多导弹数
11
12
int
indicates_x[MAX_KINGDOMS
*
MAX_INDICATES
+
MAX_SCUD
+
1
]
=
{
-
1
}
;
//
地点x坐标
13
int
indicates_y[MAX_KINGDOMS
*
MAX_INDICATES
+
MAX_SCUD
+
1
]
=
{
-
1
}
;
//
地点y坐标
14
//
所有地点信息集成存放,总数量为王国数×每个王国地点数+导弹数
15
//
这样的好处是,以后函数调用唯一id信息即可.
16
int
relation(
int
id1,
int
id2,
int
id3)
//
点与直线关系函数
17
{
//
id1->id2为向量,id3为待判断的点
18
int
temp
=
indicates_x[id1]
*
(indicates_y[id3]
-
indicates_y[id2])
19
+
indicates_x[id2]
*
(indicates_y[id1]
-
indicates_y[id3])
20
+
indicates_x[id3]
*
(indicates_y[id2]
-
indicates_y[id1]);
21
if
(temp
==
0
)
//
点在直线上的特殊情况集成处理
22
{
23
if
(indicates_x[id2]
==
indicates_x[id1])
24
{
25
if
(indicates_y[id1]
>
indicates_y[id2])
26
temp
=
indicates_y[id3]
-
indicates_y[id2];
27
else
temp
=
indicates_y[id2]
-
indicates_y[id3];
28
}
29
else
30
{
31
if
(indicates_x[id1]
>
indicates_x[id2])
32
temp
=
indicates_x[id3]
-
indicates_x[id2];
33
else
temp
=
indicates_x[id2]
-
indicates_x[id3];
34
}
35
}
36
return
temp;
37
}
38
int
kingdomarea(
int
id1,
int
id2)
//
王国面积累加函数
39
{
40
return
indicates_x[id2]
*
indicates_y[id1]
41
-
indicates_x[id1]
*
indicates_y[id2];
42
}
43
44
int
main()
45
{
46
int
kingdom_area
=
0
, i, j, k, max_id, start_id, top_id;
47
//
kingdom_area 王国面积, start_id为向量起点,max_id为向量终点,top_id卷包裹的起点
48
int
surrounds_number, indicates_id
=
1
, kingdom_number
=
0
;
49
//
surrounds_number王国凸包顶点数,kingdom_number王国数.indicates_id地点id计数器
50
int
SCUD_idstart
=
MAX_KINGDOMS
*
MAX_INDICATES
+
1
, SCUD_idend
=
SCUD_idstart;
51
//
SCUD_idstart导弹信息起始id , SCUD_idend 导弹信息结束id
52
int
kingdom[MAX_KINGDOMS][MAX_INDICATES];
//
记录凸包(王国)向量序列.
53
int
kingdom_surrounds_number[MAX_KINGDOMS
+
1
];
//
记录凸包(王国)顶点数
54
int
kingdom_startid[MAX_KINGDOMS], kingdom_endid[MAX_KINGDOMS];
55
//
记录某个王国内地点的起始id和终止id
56
int
bool_indicates[MAX_KINGDOMS
*
MAX_INDICATES
+
1
]
=
{
0
}
;
57
//
标记地点是否已作为凸包顶点.
58
59
while
(
1
)
//
王国信息输入
60
{
61
scanf(
"
%d
"
,
&
k);
62
if
(k
==
-
1
)
break
;
63
kingdom_startid[kingdom_number]
=
indicates_id;
64
kingdom_endid[kingdom_number]
=
indicates_id
+
k;
65
top_id
=
0
;
66
for
(i
=
0
; i
<
k; i
++
)
67
{
68
scanf(
"
%d%d
"
,
&
indicates_x[indicates_id],
&
indicates_y[indicates_id]);
69
if
(indicates_y[indicates_id]
>
indicates_y[top_id]
70
||
(indicates_y[indicates_id]
==
indicates_y[top_id]
71
&&
indicates_x[indicates_id]
>
indicates_x[top_id]))
72
top_id
=
indicates_id;
//
找出每个王国卷包裹的起始地点
73
indicates_id
++
;
74
}
75
kingdom[kingdom_number][
0
]
=
top_id;
76
kingdom_number
++
;
77
}
78
79
for
(i
=
0
; i
<
kingdom_number; i
++
)
//
处理单个王国的凸包信息
80
{
81
start_id
=
kingdom[i][
0
];
82
surrounds_number
=
0
;
83
do
{
84
max_id
=
kingdom_startid[i]
+
(kingdom_startid[i]
==
start_id);
85
for
(j
=
kingdom_startid[i]; j
<
kingdom_endid[i]; j
++
)
86
{
87
if
(bool_indicates[j]
==
1
||
j
==
max_id
||
j
==
start_id)
continue
;
88
if
(relation(start_id, max_id,j)
<
0
) max_id
=
j;
89
}
90
bool_indicates[max_id]
=
1
;
91
kingdom[i][
++
surrounds_number]
=
max_id;
92
start_id
=
max_id;
93
}
while
(start_id
!=
kingdom[i][
0
]);
94
kingdom_surrounds_number[i]
=
surrounds_number;
95
}
96
97
while
(scanf(
"
%d%d
"
,
&
indicates_x[SCUD_idend],
&
indicates_y[SCUD_idend])
!=
EOF)
98
SCUD_idend
++
;
99
//
输入导弹信息
100
101
for
(i
=
0
; i
<
kingdom_number; i
++
)
//
处理导弹攻击
102
{
103
for
(k
=
SCUD_idstart; k
<
SCUD_idend; k
++
)
104
{
105
for
(j
=
0
; j
<
kingdom_surrounds_number[i]; j
++
)
106
if
(relation(kingdom[i][j], kingdom[i][j
+
1
], k)
<
0
)
break
;
107
if
(j
==
kingdom_surrounds_number[i])
break
;
108
}
109
if
(k
==
SCUD_idend)
continue
;
110
for
(j
=
0
; j
<
kingdom_surrounds_number[i]; j
++
)
111
kingdom_area
+=
kingdomarea(kingdom[i][j], kingdom[i][j
+
1
]);
112
}
113
114
printf(
"
%.2f\n
"
, kingdom_area
/
2.0
);
115
return
0
;
116
}