1457土地划分【SGOI-12】.doc

土地划分【SGOI-12】
Time Limit:10000MS  Memory Limit:65536K
Total Submit:0 Accepted:0
Description
土地划分



Input
Output
Sample Input
12
10 41 15 41
15 41 20 41
10 36 15 36
15 36 17 36
10 31 15 31
15 31 20 31
10 41 10 36
10 36 10 31
15 41 17 38
17 38 17 36
15 36 15 31
20 41 20 31
Sample Output
4 1
6 1
7 1
Source
题意描述
农场主拥有一块土地,土地中有篱笆隔开,要我们求出每类土地包含的线段数以及该类土地的数目。
注意:。
。
算法分析
由于有注意事项1与2的提示,我们很容易设计如下算法:
,
,所以我们可以从外轮廓的每一条边开始,按顺时针方向搜索每个小多边形。注意:有可能一个小多边形与土地轮廓的两条或两条以上的边重合,所以搜索时要注意判重。
题目构图:
程序:
var i,j,n,m,x1,y1,x2,y2,i1,i2,la:longint;
tot,a,b,x,y:array[0..801] of longint;
use:array[1..800] of boolean;
g:array[0..801,0..801] of integer;
function get(xx,yy:longint):longint; {给每个坐标进行编号}
var i:longint;
begin
i:=1;
while (i<=n) and ((x[i]<>xx) or (y[i]<>yy)) do inc(i);
if i>n then begin
inc(n); x[n]:=xx; y[n]:=yy;
end;
exit(i);
end;
function ni(x1,y1,x2,y2,x3,y3:longint):boolean;{对判断点x3在向量x1x2的顺(true)或逆方向(false),和在同一直线上(false)}
begin
if (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1)>0 then exit(true)
else exit(false);
end;
procedure mark; {进行最外围的线段的记录}
var i,k,first,last,now:longint;
can:boolean;
begin
fillchar(a,sizeof(a),0);
k:=1;
for i:=2 to n do
if (y[k]>y[i]) or ((x[k]>x[i]) and (y[k]=y[i])) then
k:=i; {找出在左下角的点}
x[0]:=x[k]-1; y[0]:=y[k];