solution from here
题意:
给你一颗n个点的无根树,及平面上的n个点,将它们一一对应,不允许线段交叉.
随便输出一个解,题目保证没有三点共线.
solution:
思路:极角排序+dfs分治
函数solve(l,r,x,fa)
l r为x及其子树对应的平面坐标区间
对于一棵树,把l~r中最左下角的那个点作为根
对剩下的点极角排序,
对于每一棵子树,按需分配－－即分配等同于其大小的点数
如上
code
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define N 2000 #define ll long long using namespace std; ll n; struct sett{ ll x,y,id; }p[N],plk; struct zero{ ll nxt,to; }edge[N<<1]; ll tot=0,head[N]; ll size[N]; ll Ans[N]; void add_edge(ll a,ll b){ edge[++tot]=(zero){head[a],b}; head[a]=tot; } void aux(ll x,ll fa){//预处理子树大小 size[x]=1; for(ll i=head[x];i;i=edge[i].nxt){ ll to=edge[i].to; if(to==fa)continue; aux(to,x); size[x]+=size[to]; } } bool cmp(sett a,sett b){ ll ax=a.x-plk.x,ay=a.y-plk.y,bx=b.x-plk.x,by=b.y-plk.y; if(ax>=0&&bx<=0)return 1; if(ax<=0&&bx>=0)return 0; return (ax*by>ay*bx); } void solve(ll l,ll r,ll x,ll fa){//dfs分治 ll poss=l; for(ll i=l+1;i<=r;i++) if(p[i].x<p[poss].x||(p[i].x==p[poss].x&&p[i].y<p[poss].y))poss=i; swap(p[l],p[poss]); plk=p[l]; Ans[p[l].id]=x; sort(p+l+1,p+r+1,cmp);//极角排序 ll now=l+1; for(ll i=head[x];i;i=edge[i].nxt){
ll to=edge[i].to; if(to==fa)continue; solve(now,now+size[to]-1,to,x);//分配 now+=size[to]; } } int main(){ scanf("%lld",&n); for(ll i=1;i<n;i++){ ll a,b; scanf("%lld%lld",&a,&b); add_edge(a,b); add_edge(b,a); } for(ll i=1;i<=n;i++){ ll x,y; scanf("%lld%lld",&x,&y); p[i]=(sett){x,y,i}; } aux(1,0); solve(1,n,1,0); for(ll i=1;i<=n;i++) printf("%lld ",Ans[i]); }
原文：https://www.cnblogs.com/stepsys/p/10370258.html