Отримання знань

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на Pascal:

program PKU1034;
const maxn = 101;

type integer = longint;
     node = array[1..2] of integer;

var g: array[1..maxn, 1..maxn] of boolean;
    a, b: array[1..maxn] of node;
    x, y: array[1..maxn] of integer;
    n, m: integer;

function dis(var p, q: node): extended;
begin
  dis := sqrt(sqr(p[1] - q[1]) + sqr(p[2] - q[2]));
end;

procedure prepare;
var i, j: integer;
begin
  fillchar(g, sizeof(g), false);
  readln(n, m);
  for i := 1 to n do read(a[i, 1], a[i, 2]); n := n - 1;
  for i := 1 to m do read(b[i, 1], b[i, 2]);
  for i := 1 to n do
    for j := 1 to m do
      g[i, j] := dis(a[i], b[j]) + dis(a[i + 1], b[j]) <= dis(a[i], a[i + 1]) * 2;
end;

var visit: array[1..maxn] of boolean;

function find(k: integer): boolean;
var i: integer;
begin
  find := true;
  for i := 1 to m do if g[k, i] and (not visit[i]) then begin
    visit[i] := true;
    if (y[i] = 0) or find(y[i]) then begin
      y[i] := k;
      x[k] := i;
      exit;
    end;
  end;
  find := false;
end;

procedure main;
var i, ans: integer;
begin
  fillchar(x, sizeof(x), 0);
  fillchar(y, sizeof(y), 0);
  ans := n + 1;
  for i := 1 to n do if x[i] = 0 then begin
    fillchar(visit, sizeof(visit), false);
    if find(i) then ans := ans + 1;
  end;
  writeln(ans);
  for i := 1 to n + 1 do begin
    write(a[i, 1], ' ', a[i, 2], ' ');
    if x[i] > 0 then write(b[x[i], 1], ' ', b[x[i], 2], ' ');
  end;
  writeln;
end;

begin
  prepare;
  main;
end.

   Пример решения на Pascal:

#include < cmath >
#include < iostream >
using namespace std;

const int MAXN=100, MAXE=10000;
typedef struct Edge{
    int x, y, next;
}Edge;
Edge es[MAXE];
int eid, firstX[MAXN], linkY[MAXN];
bool ry[MAXN];

int x[MAXN], y[MAXN], xx[MAXN], yy[MAXN], n, m;

void inline addEdge(int start, int end);
void inline clr();
bool find(int u);

void addEdge(int start, int end){
    es[eid].x=start, es[eid].y=end;
    es[eid].next=firstX[start], firstX[start]=eid; eid++;
}
void clr(){
    eid=0,
    memset((void*)firstX, 0xff, sizeof(firstX)),
    memset((void*)linkY, 0xff, sizeof(linkY));
}
bool find(int u){
    for(int e=firstX[u]; e!=-1; e=es[e].next){
        if(!ry[es[e].y]){
            ry[es[e].y]=true;
            if(linkY[es[e].y]==-1||find(linkY[es[e].y])){
                linkY[es[e].y]=u; return true;
            }
        }
    }
    return false;
}

int main()
{
    int res(0);
    cin>>n>>m;
    for(int i=0; i<n; i++) cin>>x[i]>>y[i];
    for(int i=0; i<m; i++) cin>>xx[i]>>yy[i];
    clr();
    for(int i=0; i<n-1; i++){
        double dis=sqrt((double)((x[i]-x[i+1])*(x[i]-x[i+1])+(y[i]-y[i+1])*(y[i]-y[i+1])));
        for(int j=0; j<m; j++){
            double dis1=sqrt((double)((x[i]-xx[j])*(x[i]-xx[j])+(y[i]-yy[j])*(y[i]-yy[j]))),
                dis2=sqrt((double)((x[i+1]-xx[j])*(x[i+1]-xx[j])+(y[i+1]-yy[j])*(y[i+1]-yy[j])));
            if(2*dis>=dis1+dis2) addEdge(j, i);
        }
    }
    for(int i=0; i<m; i++){
        memset((void*)ry, 0, sizeof(bool)*n);
        res+=find(i);
    }
    cout<<(res+n)<<endl;
    for(int i=0; i<n; i++){
        if(i!=n-1) cout<<x[i]<<" "<<y[i]<<" ";
        else cout<<x[i]<<" "<<y[i];
        if(linkY[i]!=-1) cout<<xx[linkY[i]]<<" "<<yy[linkY[i]]<<" ";
    }
    cout<<endl;

    return 0;
}