题目链接:http://poj.org/problem?id=1034
分析:
读题是多么的重要。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; struct node { int v,next; }edge[10010]; int head[300]; struct point{ int x,y; }in_set[300],out_set[300]; int n,m,cnt; bool visit[300]; int match[300]; void add_edge(int x,int y) { edge[++cnt].v=y; edge[cnt].next=head[x]; head[x]=cnt; return ; } double Val(point a,point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } void creat_pg() { for(int i=1;i<=m;++i) { for(int j=1;j<n;++j) { double k1=Val(out_set[i],in_set[j]); double k3=Val(out_set[i],in_set[j+1]); double k2=Val(in_set[j],in_set[j+1]); if(k1+k3<k2*2){ add_edge(i,j); } } } return ; } int Hungary(int x) { for(int i=head[x];~i;i=edge[i].next) { int v=edge[i].v; if(!visit[v]) { visit[v]=true; if(!match[v]||Hungary(match[v])) { match[v]=x; return true; } } } return false; } int main() { memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) { scanf("%d%d",&in_set[i].x,&in_set[i].y); } for(int i=1;i<=m;++i) { scanf("%d%d",&out_set[i].x,&out_set[i].y); } creat_pg(); for(int i=1;i<=m;++i) { memset(visit,false,sizeof(visit)); Hungary(i); } int ans=0; for(int i=1;i<=n;++i) { if(match[i])ans++; } printf("%d\n",ans+n); for(int i=1;i<=n;++i) { printf("%d %d ",in_set[i].x,in_set[i].y); if(match[i])printf("%d %d ",out_set[match[i]].x,out_set[match[i]].y); } return 0; } |
