Форум Всеукраїнської інтернет-олімпіади NetOI

{$APPTYPE CONSOLE}
{$B-,R-,O+}
const
 m=4;
 n=20;
 v=1;
 maxcrd=10;
var
 i:smallint; 
begin
 assign(output,'patrol.in');
 rewrite(output);
 randomize;
 write(m,' ',v,' ',n);
 for i:=1 to n do
  write(' ',maxcrd*random,' ',maxcrd*random);
 writeln; 
 close(output);
end.

#include <cstdio>
#include <cmath>

#define maxn 1000
#define maxm 1000
#define maxcrd 2000000
#define inf 4000001

#define sqr(x) ((x)*(x))
#define dist(x1,y1,x2,y2) (sqrt(sqr(x1-x2)+sqr(y1-y2)))
#define min(a,b) ((a)<(b)?(a):(b))

struct point{double x,y;};

int n,m,i,j;
double v,len,gap,time,tek,mindist,mintime;
point a[maxn+2];
point start[maxm];
int pos[maxm];
double t[maxm];
double l[maxn];
point angle[maxn];//x is cos, y is sin;

inline void check(int i,int j,double left,double tek)
{
    double A,B,C,tekmin,out;
    A=v*v*(sqr(angle[pos[i]].x-angle[pos[j]].x)+sqr(angle[pos[i]].y-angle[pos[j]].y));
    B=2*v*((start[i].x-start[j].x)*(angle[pos[i]].x-angle[pos[j]].x)+(start[i].y-start[j].y)*(angle[pos[i]].y-angle[pos[j]].y));
    C=sqr(start[i].x-start[j].x)+sqr(start[i].y-start[j].y);
    if(fabs(A)<1e-9)
    {
      if(B>0) 
       tekmin=0;else
       tekmin=tek;
    }else
    {
      out=min(dist(start[i].x,start[i].y,a[pos[i]].x,a[pos[i]].y)/v,dist(start[j].x,start[j].y,a[pos[j]].x,a[pos[j]].y)/v); 
      if(-B/(2*A)<-out)
       tekmin=-out;else
      if(-B/(2*A)>tek)
       tekmin=tek;else
       tekmin=-B/(2*A);
      if (tekmin+left<0)
       tekmin=-left;
    }
    //we will use mindist <=> sqr(mindist)
    if(A*tekmin*tekmin+B*tekmin+C<mindist)
    {
      mindist=A*tekmin*tekmin+B*tekmin+C;
      mintime=left+tekmin;
    }
}

int main()
{
    mindist=1e50;
    scanf("%d%lf%d",&m,&v,&n);
    for(i=0;i<n;i++)
     scanf("%lf%lf",&a[i].x,&a[i].y);
    a[n]=a[0];
    a[n+1]=a[1];
    for(len=0,i=0;i<n;i++)
    {
        l[i]=dist(a[i].x,a[i].y,a[i+1].x,a[i+1].y);
        angle[i].x=(a[i+1].x-a[i].x)/l[i];
        angle[i].y=(a[i+1].y-a[i].y)/l[i];
        len+=l[i];
    }
    gap=len/m;
    time=gap/v;
    start[0]=a[0];
    pos[0]=0;
    t[0]=min(l[0]/v,time);
    tek=0;
    j=0;
    for(i=0;i<n;i++)
    {
        tek+=l[i];
        if (tek>=gap-1e-9)
        {
            j++;
            pos[j]=i;
            tek-=gap;
            start[j].x=a[i].x+(l[i]-tek)*angle[i].x;
            start[j].y=a[i].y+(l[i]-tek)*angle[i].y;
            t[j]=min(dist(start[j].x,start[j].y,a[i+1].x,a[i+1].y)/v,time);
        }
    }
    tek=0;
    while(tek<=time+1e-9)
    {
      for(j=0,i=1;i<m;i++)
       if(t[i]<t[j])
        j=i;
      for(i=0;i<m;i++)
       if(i!=j)
        check(i,j,tek,t[j]);    
      for(i=0;i<m;i++)
      {
        start[i].x+=v*t[j]*angle[pos[i]].x;
        start[i].y+=v*t[j]*angle[pos[i]].y;
      }
      tek+=t[j];
      for(i=0;i<m;i++)
       if(i!=j)
        t[i]-=t[j];
      pos[j]=(pos[j]+1)%n;
      t[j]=min(l[pos[j]]/v,time+2e-9-tek);
    }
    printf("%.9lf %.9lf\n",mintime,sqrt(mindist));
    return 0;
}

#include <cstdio>
#include <cmath>

#define maxn 1000
#define maxm 1000
#define maxcrd 1000000
#define inf 2000001
#define eps 1e-4

#define sqr(x) ((x)*(x))
#define dist(x1,y1,x2,y2) (sqrt(sqr(x1-x2)+sqr(y1-y2)))
#define min(a,b) ((a)<(b)?(a):(b))

struct point{double x,y;};

int n,m,i,j;
double v,len,gap,time,tek,mindist,mintime;
point a[maxn+2];
point start[maxm];
int pos[maxm];
double t[maxm];
double l[maxn];
point angle[maxn];//x is cos, y is sin;

inline void check()
{
    int i,j;
    for(i=0;i<m;i++)
     for(j=i+1;j<m;j++)
      if(dist(start[i].x,start[i].y,start[j].x,start[j].y)<mindist)
      {
        mindist=dist(start[i].x,start[i].y,start[j].x,start[j].y);
        mintime=tek;
      }
}

int main()
{
    mindist=1e50;
    scanf("%d%lf%d",&m,&v,&n);
    for(i=0;i<n;i++)
     scanf("%lf%lf",&a[i].x,&a[i].y);
    a[n]=a[0];
    a[n+1]=a[1];
    for(len=0,i=0;i<n;i++)
    {
        l[i]=dist(a[i].x,a[i].y,a[i+1].x,a[i+1].y);
        angle[i].x=(a[i+1].x-a[i].x)/l[i];
        angle[i].y=(a[i+1].y-a[i].y)/l[i];
        len+=l[i];
    }
    gap=len/m;
    time=gap/v;
    start[0]=a[0];
    pos[0]=0;
    t[0]=min(l[0]/v,time);
    tek=0;
    j=0;
    for(i=0;i<n;i++)
    {
        tek+=l[i];
        if (tek>=gap-1e-9)
        {
            j++;
            pos[j]=i;
            tek-=gap;
            start[j].x=a[i].x+(l[i]-tek)*angle[i].x;
            start[j].y=a[i].y+(l[i]-tek)*angle[i].y;
            t[j]=min(dist(start[j].x,start[j].y,a[i+1].x,a[i+1].y)/v,time);
        }
    }
    tek=0;
    check();
    while(tek<=time-eps)
    {
      for(i=0;i<m;i++)
      {
        start[i].x+=v*eps*angle[pos[i]].x;
        start[i].y+=v*eps*angle[pos[i]].y;
        if(dist(start[i].x,start[i].y,a[pos[i]+1].x,a[pos[i]+1].y)+dist(start[i].x,start[i].y,a[pos[i]].x,a[pos[i]].y)>l[pos[i]]+1e-5)
        {
          pos[i]++;
          start[i]=a[pos[i]];
        }
      }
      tek+=eps;
      check();
    }
    printf("%.9lf %.9lf\n",mintime,mindist);
    return 0;
}