URAL/1065

来自"NOCOW"

先连边，i点到j点有边的时候，当前仅当i到j这一块中不包含任何纪念碑,可以以i为一端点，以j,j-1为另外两个点的三角形来判断其中是否包含纪念碑;

然后就是求最小环了;

特别注意两点：

（1）当前三角形如果为一条直线则跳过

（2）最后的路线不能为一条直线

program djy;
var
  x,y:array[1..100] of int64;
  xx,yy:array[1..1000] of int64;
  flag:array[1..100,1..100] of boolean;
  dis:array[1..100,1..100] of extended;
  n,m:longint;
procedure init;
var
  i:longint;
begin
  readln(n,m);
  for i:=1 to n do
  begin
    readln(x[i],y[i]);
    x[n+i]:=x[i];
    y[n+i]:=y[i];
  end;
  for i:=1 to m do
  readln(xx[i],yy[i]);
end;
function chaji(x1,y1,x2,y2:int64):int64;
begin
  chaji:=x1*y2-x2*y1;
end;
function cross(x1,y1,x2,y2,x3,y3,x4,y4:int64):boolean;     {判断线段相交}
begin
  if chaji(x2-x1,y2-y1,x3-x1,y3-y1)*chaji(x2-x1,y2-y1,x4-x1,y4-y1)<0 then
  if chaji(x4-x3,y4-y3,x1-x3,y1-y3)*chaji(x4-x3,y4-y3,x2-x3,y2-y3)<0 then exit(true);
  exit(false);
end;
function inside(x1,y1,x2,y2,x3,y3,p,q:int64):boolean;    {判断(p,q)是否在三角形内，用（p,q)分别向三顶点连一条直线，看是否与剩下两点构成的直线相交}
begin
  if cross(x1,y1,p,q,x2,y2,x3,y3)=true then exit(false);
  if cross(x2,y2,p,q,x3,y3,x1,y1)=true then exit(false);
  if cross(x3,y3,p,q,x1,y1,x2,y2)=true then exit(false);
  exit(true);
end;
procedure prepare;
var
  i,j,k:longint;
  check:boolean;
begin
  for i:=1 to n do
  begin
    flag[i,i+1]:=true;
    for j:=i+2 to i+n-1 do
    begin
      check:=true;
      if chaji(x[i]-x[j-1],y[i]-y[j-1],x[i]-x[j],y[i]-y[j])<>0 then   {检查三角形是否为一直线}
      begin
        for k:=1 to m do
        if inside(x[i],y[i],x[j-1],y[j-1],x[j],y[j],xx[k],yy[k])=true then check:=false;
      end;
      if check=true then flag[i,j]:=true
      else break;
    end;
  end;
end;
procedure main;
var
  i,j,k:longint;
begin
  for i:=1 to n do
  for j:=i+1 to i+n-1 do
  if flag[i,j]=true then dis[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]))
  else dis[i,j]:=100000000;
  for k:=1 to n do
  for i:=1 to k-1 do
  for j:=k+1 to n do
  if dis[i,k]+dis[k,j]<dis[i,j] then dis[i,j]:=dis[i,k]+dis[k,j];
end;
procedure print;
var
  i,j,k:longint;
  ans:extended;
begin
  ans:=100000000;
  for i:=1 to n do
  for j:=i+1 to n do
  for k:=j+1 to n do                         {检查路线是否为一条直线}
  if (dis[i,j]+dis[j,k]+dis[k,i+n]<ans) and (chaji(x[i]-x[j],y[i]-y[j],x[i]-x[k],y[i]-y[k])<>0) then ans:=dis[i,j]+dis[j,k]+dis[k,i+n];
  writeln(ans:0:2);
end;
begin
  init;
  prepare;
  main;
  print;
end.