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.
Пример решения на С++:
Код:
#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; }