题目大意:给你一个平面图,平面被分成了若干个区域,求出每个区域与之相邻的区域,数据保证区域数不超过500;
有数据范围可以看出要求是低于N3的算法。
我的做法是:
1.将每一条线段AB拆成两条有向线段AB与BA,然后将所有有向线段AB与从B点引出的线段中位于AB顺时针方向的第一条线段连有向边(BA与AB的夹角为2PI,而不是0)。这样对所有的线段做一次DFS之后就能将图中的封闭区域全部求出来,这样出了某个区域包含的区域,其他相邻的区域都可以求出来了;
2.可以使用环顾法求出各个区域之间的包含关系,这个包含关系类似于一棵树,然后用拓扑序,先处理叶子节点,这样可以把包含关系也求出来。
这个方法是我觉得最好实现的方法了。
总之既然是计算几何题就肯定有很多细节的,最后还是拿了几组数据来调才A的(数据很不好生成。。)
另外就是发现math库里面直接就有求极角的函数了,那就是arctan2!以后不用自己写极角了,每次都要重新推一遍,囧。
code:
operator /(a,b:xl)c:longint;begin c:=a.x*b.x+a.y*b.y end;
operator *(a,b:xl)c:longint;begin c:=a.x*b.y-a.y*b.x end;
function mo(a:xl):real;begin mo:=sqrt(a.x*a.x+a.y*a.y) end;
operator -(a,b:xl)c:xl;begin c.x:=a.x-b.x;c.y:=a.y-b.y end;
function jiao(a,b:xl):real;
begin
jiao:=(a/b)/(mo(a)*mo(b));
if jiao=1 then jiao:=0 else jiao:=arccos(jiao);
if a*b<0 then jiao:=-jiao;
end;
function find(dd:xl):longint;var i:longint;
begin
for i:=1 to dt do
if (dd.x=dp[i].x)and(dd.y=dp[i].y) then exit(i);
inc(dt);dp[dt]:=dd;find:=dt;
end;
procedure link(i,j:longint);
begin
inc(t);next[t]:=d[i];d[i]:=t;p[t]:=j;b[t]:=t+1;
inc(t);next[t]:=d[j];d[j]:=t;p[t]:=i;b[t]:=t-1;
end;
begin
assign(input,'risk.in');reset(input);
assign(output,'risk.out');rewrite(output);
readln(n,m);
for i:=1 to n do readln(h[i].x,h[i].y);
for i:=1 to m do begin
readln(ss.x,ss.y,tt.x,tt.y);
link(find(ss),find(tt));
end;
for i:=1 to t do begin
jd[i]:=-9;
k:=d[p[i]];j:=p[k];
t1:=dp[p[i]]-dp[p[b[i]]];
while k<>0 do begin
if k<>b[i] then begin
t2:=jiao(t1,dp[j]-dp[p[i]]);
if t2>jd[i] then begin
jd[i]:=t2;
go[i]:=k;
end;
end;
k:=next[k];j:=p[k];
end;
end;
for i:=1 to t do
if fo[i]=0 then begin
k:=i;
t2:=0;
inc(mt);
v[mt]:=0;
repeat
t2:=t2+jd[k];
inc(v[mt]);
k:=go[k];
until i=k;
if t2>0 then begin
repeat
fo[k]:=mt;
k:=go[k];
until i=k;
fir[mt]:=i;
end else begin
repeat
fo[k]:=-1;
k:=go[k];
until i=k;
dec(mt);
end;
end;
for i:=1 to n do
for j:=1 to mt do begin
k:=fir[j];
t2:=0;
repeat
t2:=t2+jiao(dp[p[b[k]]]-h[i],
dp[p[k]]-h[i]);
k:=go[k];
until k=fir[j];
c[i,j]:=abs(t2-2*pi)<1e-6;
inc(g[j],ord(c[i,j]));
a[i,j]:=c[i,j];
end;
for l:=1 to n do begin
for i:=1 to mt do
if g[i]=1 then break;
for j:=1 to n do
if c[j,i] then break;
s[i]:=j;q[j]:=i;
for k:=1 to mt do dec(g[k],ord(c[j,k]));
for k:=1 to mt do c[j,k]:=false;
for j:=1 to n do
if (j<>s[i])and a[j,i] and (v[q[j]]<>0) then begin
v[q[j]]:=0;
e[s[i],j]:=true;
e[j,s[i]]:=true;
end;
k:=fir[i];
repeat
dec(v[fo[b[k]]]);
k:=go[k];
until k=fir[i];
end;
for i:=1 to mt do begin
k:=fir[i];
repeat
e[s[fo[b[k]]],s[i]]:=true;
k:=go[k];
until k=fir[i];
end;
for i:=1 to n do begin
t:=0;
for j:=1 to n do inc(t,ord(e[i,j]));
write(t,' ');
for j:=1 to n do
if e[i,j] then write(j,' ');
writeln;
end;
close(input);close(output);
end.