Home > OI > Sgu 128

Sgu 128


这题纠结了挺久,近来实在是被sgu上计如潮水的计算几何题给吓到了,这又是其中 一道,而且还要用线段树。

主要参考了2004年林涛的论文《线段树的应用》例题一, 以下引用自原论文:

从该题的要求入手,先构出符合要求的图,再解决线段长度之和最小 的问题。

1    题目显然要求一个以给定的 N个点为顶点的 N多边形。所有线段都要和坐标轴平行,所以每个点只能与上下左右四个点相连。由于与一个点相连的两条线段成 90度,每个顶点必须与一条平行于 X轴和一条平行于 Y轴的线段相连。

2    将所有点排序后发现,在同一水平线上 的点中,设这些点为 P1,P2,P3, P4……Pn,P1要有一条平行于 X轴的线段与其相连,就必须连它右边的点 ——P2,而 P3如果再连 P2,P2就有两条平行于 X轴的线段和它相连,所以 P3只能连 P4,P5只能连 P6……,同一垂直线上的点也是如此,所以线段的构造是唯一的,那么最小长度的问题就解决了。

3    由于解是唯一的,而是否相连只要广度扩展就可以判断了,所以 关键在于判断由上述方法所构出线段是否合法——满足线段不在 N个点之外自交。

4.由于 所有线段与坐标轴之一平行,有明显的区间性,可以想到用线段树判断是否自交。

(1)由于只可能是与 X轴平行的线段和与 Y轴的线段相交,所以可以只考虑与 Y轴平行的线段是否有线段与之相交。如果线段 (x,y1)-(x,y2)与线段(x1,y)-(x2,y)相交,那么应该符合(x1<x<x2)、 (y1<y<y2),由条件(x1<x<x2),可以想到先把所有的线段按 X坐标排序。本题要注意的是,线段在端点重合不算自交,所以 X轴坐标相同时,事件的顺序要恰当处理。右端点优先,与 Y轴平行的线段其次,然后到左端点。

(2)将 Y轴表示的区间建立线段树。排序后,每个线段或线段的端点称为一个事件,如左图,S1,S2,S3,S4分别为一个事件。按 X坐标由小到大,扫描所有事件,如果遇到平行于 X轴线段的左端点,则按它的 Y坐标当成一个点,插入到表示 Y轴区间的线段树中,如果遇到平行于 X轴线段的右端点,则把它代表的点从线段树中删除。如果遇到与 Y轴平行的线段 L1(x,y1)-(x,y2),假设有线段 L2(x1,y)-(x2,y)与之相交,由(x1<x<x2)可知 L2的左端点已经被扫描过,那么 L2代表的点已经插入线段树中;L2的右端点还没被扫描过,说明 L2代表的点依然存在于线段树之中。换而言之,只要还在线段树中的点,就满足 (x1<x<x2)。要判断(y1<y<y2)的条件是否满足,可以在线段树中查找[y1+1,y2-1](在端点处可以相交) 区间内是否有点存在,如果存在,就说明有线段和它相交,该图形不合法。

(3)具体的实现时要注意线段树每个节点增加一个变量记录该区间内的点 数,线段树的单位元(叶子节点)改成一个点,而不是一条单位线段。每次插入和删除后,只要对相关节点的变量进行改动就可以了。

这里稍作一下解释,按x坐标排序时,对于平行于x轴的线段,要拆 成左端点和右端点;对于平行于y轴的线段,则直接处理,若某个比较中,出现坐标值相同,则按”右端点优先,与 Y轴平行的线段其次,然后到左端点“来处理。

sgu128

1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 struct type_pix
5 {
6     int x,y,id;
7 } p[10001];
8 struct type_seg
9 {
10     int x1,x2,y1,y2;
11 } edge[10001];
12 struct type_event
13 {
14     int id,x,type;
15 } event[30001];
16 struct type_tree
17 {
18     int a,b,t,
19     leftson,rightson;
20 } tree[100001];
21 int n,num,connect[10001][2],ans,cnt,maxy=-1,miny=99999,treenum;
22 char vis[10001];
23 void imp()
24 {
25     printf(“0\n”);
26     exit(0);
27 }
28 void init()
29 {
30     scanf(“%d”,&n);
31     for(int i=1;i<=n;++i){
32         scanf(“%d%d”,&p[i].x,&p[i].y);
33         p[i].id=i;
34         maxy=p[i].y>maxy?p[i].y:maxy;
35         miny=p[i].y<miny?p[i].y:miny;
36     }
37     if(n&1)
38         imp();
39 }
40 int cmp1(const void *a, const void *b)
41 {
42     struct type_pix *c=(type_pix *) a;
43     struct type_pix *d=(type_pix *) b;
44     if(c->y!=d->y) return c->y-d->y;
45     return c->x-d->x;
46 }
47 int cmp2(const void *a, const void *b)
48 {
49     struct type_pix *c=(type_pix *) a;
50     struct type_pix *d=(type_pix *) b;
51     if(c->x!=d->x) return c->x-d->x;
52     return c->y-d->y;
53 }
54 int cmp3(const void *c, const void *d)
55 {
56     struct type_event *a=(type_event*) c;
57     struct type_event *b=(type_event*) d;
58     if(a->x != b->x) return a->x – b->x;
59     return a->type – b->type;
60 }
61 void createpic()
62 {
63     qsort(p+1,n,sizeof(type_pix),cmp1);
64     for(int i=1;i<=n;i+=2)
65     {
66         if(p[i].y!=p[i+1].y)
67             imp();
68         edge[++num].x1=p[i].x;
69         edge[num].x2=p[i+1].x;
70         edge[num].y1=edge[num].y2=p[i].y;
71         connect[p[i].id][0]=p[i+1].id;
72         connect[p[i+1].id][0]=p[i].id;
73         ans+=p[i+1].x-p[i].x;
74         event[++cnt].type=0;
75         event[cnt].x=p[i+1].x;
76         event[cnt].id=num;
77         event[++cnt].type=2;
78         event[cnt].x=p[i].x;
79         event[cnt].id=num;
80     }
81     qsort(p+1,n,sizeof(type_pix),cmp2);
82     for(int i=1;i<=n;i+=2)
83     {
84         if(p[i].x!=p[i+1].x)
85             imp();
86         edge[++num].y1=p[i].y;
87         edge[num].y2=p[i+1].y;
88         edge[num].x1=edge[num].x2=p[i].x;
89         connect[p[i].id][1]=p[i+1].id;
90         connect[p[i+1].id][1]=p[i].id;
91         ans+=p[i+1].y-p[i].y;
92         event[++cnt].type=1;
93         event[cnt].x=p[i].x;
94         event[cnt].id=num;
95     }
96 }
97 void dfs(int now)
98 {
99     vis[now]=true;
100     if(!vis[connect[now][0]])
101         dfs(connect[now][0]);
102     if(!vis[connect[now][1]])
103         dfs(connect[now][1]);
104 }
105 void check_link()
106 {
107     dfs(1);
108     for(int i=1;i<=n;++i)
109         if(!vis[i])
110             imp();
111 }
112 int segtree(int a, int b)
113 {
114     int now=++treenum;
115     tree[now].a=a;
116     tree[now].b=b;
117     if((a+b>>1)>a)
118     {
119         tree[now].leftson=segtree(a,a+b>>1);
120         tree[now].rightson=segtree(a+b>>1,b);
121     }
122     return now;
123 }
124 void insertv(int y, int id)
125 {
126     int a=tree[id].a,b=tree[id].b;
127     if(b-a<=1)
128         ++tree[id].t;
129     else
130     {
131         if(y<=a+b>>1)
132             insertv(y,tree[id].leftson);
133         else
134             insertv(y,tree[id].rightson);
135         tree[id].t=tree[tree[id].leftson].t+tree[tree[id].rightson].t;
136     }
137 }
138 void deletev(int y, int id)
139 {
140     int a=tree[id].a,b=tree[id].b;
141     if(b-a<=1)
142         –tree[id].t;
143     else
144     {
145         if(y<=a+b>>1)
146             deletev(y,tree[id].leftson);
147         else
148             deletev(y,tree[id].rightson);
149         tree[id].t=tree[tree[id].leftson].t+tree[tree[id].rightson].t;
150     }
151 }
152 int findv(int y1, int y2, int id)
153 {
154     int a=tree[id].a,b=tree[id].b;
155     if(y1<=a&&b<=y2)
156         return tree[id].t;
157     if(b-a<=1) return 0;
158     int ans=0;
159     if(y1<=(a+b>>1))
160         ans|=findv(y1,y2,tree[id].leftson);
161     if(y2>(a+b>>1))
162         ans|=findv(y1,y2,tree[id].rightson);
163     return ans;
164 }
165 void check_cross()
166 {
167     qsort(event+1,cnt,sizeof(type_event),cmp3);
168     segtree(miny,maxy);
169     for(int i=1;i<=cnt;++i)
170     {
171         int id=event[i].id;
172         if(!event[i].type)
173             deletev(edge[id].y1,1);
174         else if(event[i].type==2)
175             insertv(edge[id].y1,1);
176         else
177             if(findv(edge[id].y1,edge[id].y2,1))
178                 imp();
179     }
180 }
181 void work()
182 {
183     createpic();
184     check_link();
185     check_cross();
186     printf(“%d\n”,ans);
187 }
188 int main()
189 {
190     init();
191     work();
192     return 0;
193 }
194
Categories: OI
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: