首页 > 代码库 > POJ 3207 Ikki's Story IV - Panda's Trick

POJ 3207 Ikki's Story IV - Panda's Trick

简单的看了2-sat……似乎还是挺神奇的东西……等大致刷完几道题再来写总结吧!

而这道题……算是2-sat的超级入门题了吧

不过题目大意也是醉了:圆上顺序排列n个点,现要在一些点间连边,规定边只能在圆内或圆外,求有没有可能不相交 。一开始想的是嗷嗷嗷,圆上两个点的连线怎么可能有什么在圆外在圆内之分,不都是弦么?后来才知道……原来两个点的连线不是直线可以使曲线……

判定是否相交很简单吧……看成是一条直线上四个点,那么如果e1.a<e2.a<e1.b<e2.b就相交啦……

都说是热身题没多难……

技术分享
type  arr1=record    a,b:longint;  end;  arr2=record    toward,next:longint;  end;var  e:array[0..3000]of arr1;  edge:array[0..3000]of arr2;  first,dfn,low,scc,p,num1,num2:array[0..3000]of longint;  chose:array[0..3000]of boolean;  time,total,tot,n,m,tail,sum:longint;procedure swap(var x,y:longint);var  i:longint;begin  i:=x;  x:=y;  y:=i;end;procedure addedge(j,k:longint);begin  inc(total);  edge[total].toward:=k;  edge[total].next:=first[j];  first[j]:=total;end;procedure add(j,k:longint);begin  addedge(j,k);  addedge(k,j);end;function check(x,y:arr1):boolean;begin  if (x.a<y.a) and (y.a<x.b) and (x.b<y.b) then exit(true);  exit(false);end;procedure tarjan(x:longint);var  i,too,j:longint;begin  inc(time);  dfn[x]:=time;  low[x]:=time;  chose[x]:=true;  inc(tail);  p[tail]:=x;  i:=first[x];  while i>0 do begin    too:=edge[i].toward;    if dfn[too]=0 then begin      tarjan(too);      if low[too]<low[x] then low[x]:=low[too];    end    else      if dfn[too]<low[x] then low[x]:=dfn[too];    i:=edge[i].next;  end;  if dfn[x]=low[x] then begin    inc(sum);    repeat      j:=p[tail];      dec(tail);      chose[j]:=false;      scc[j]:=sum;    until j=x;  end;end;procedure into;var  i,j:longint;begin  readln(n,m);  for i:=1 to m do begin    read(e[i].a,e[i].b);    if e[i].a>e[i].b then swap(e[i].a,e[i].b);    inc(tot);    num1[i]:=tot;    inc(tot);    num2[i]:=tot;  end;  for i:=1 to m-1 do    for j:=i+1 to m do      if check(e[i],e[j]) or check(e[j],e[i]) then begin        add(num1[i],num2[j]);        add(num2[i],num1[j]);      end;end;function work:boolean;var  i:longint;begin  for i:=1 to tot do    if dfn[i]=0 then tarjan(i);  for i:=1 to m do    if scc[num1[i]]=scc[num2[i]] then exit(false);  exit(true);end;begin  into;  if work then writeln(panda is telling the truth...)    else writeln(the evil panda is lying again);end.
View Code

 

POJ 3207 Ikki's Story IV - Panda's Trick