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

дистанційна підтримка освіти школярів


Задача собаки
http://acm.pku.edu.cn/JudgeOnline/problem?id=1034

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

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

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

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

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

   Пример решения на 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;
}
 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)