首页 > 代码库 > Codeforces Round #124 (Div. 1) C. Paint Tree(极角排序)

Codeforces Round #124 (Div. 1) C. Paint Tree(极角排序)

C. Paint Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with n vertexes and n points on a plane, no three points lie on one straight line.

Your task is to paint the given tree on a plane, using the given points as vertexes.

That is, you should correspond each vertex of the tree to exactly one point and each point should correspond to a vertex. If two vertexes of the tree are connected by an edge, then the corresponding points should have a segment painted between them. The segments that correspond to non-adjacent edges, should not have common points. The segments that correspond to adjacent edges should have exactly one common point.

Input

The first line contains an integer n (1?≤?n?≤?1500) — the number of vertexes on a tree (as well as the number of chosen points on the plane).

Each of the next n?-?1 lines contains two space-separated integers ui and vi (1?≤?ui,?vi?≤?n, ui?≠?vi) — the numbers of tree vertexes connected by the i-th edge.

Each of the next n lines contain two space-separated integers xi and yi (?-?109?≤?xi,?yi?≤?109) — the coordinates of the i-th point on the plane. No three points lie on one straight line.

It is guaranteed that under given constraints problem has a solution.

Output

Print n distinct space-separated integers from 1 to n: the i-th number must equal the number of the vertex to place at the i-th point (the points are numbered in the order, in which they are listed in the input).

If there are several solutions, print any of them.

Examples
Input
3
1 3
2 3
0 0
1 1
2 0
Output
1 3 2
Input
4
1 2
2 3
1 4
-1 -2
3 5
-3 3
2 0
Output
4 2 1 3
【分析】题意比较简单。给你一棵n个节点的树,再给你几何平面内的n个点,没有三点共线,
问你能不能用着n个点在几何平面内表现出来,线段除了顶点处无其他交点。

由于没有3点共线的情况,所以解总是存在的。
我们考虑以当前平面左下角的点p作为树根,对平面上的点以p做基准进行极角排序,则所有点与p点的连线都不会有除了p以外的交点。
现在我们已经会填树根处的点了,对于树根的每个子节点,我们都可以递归的处理以其为根的子树,
假设该子树包含x个节点,我们考虑以一根从p出发,长度不限的射线,从p的正下方开始按逆时针扫过去,
直到扫过的平面包含x个节点即可停止。此时扫过的平面即为该子树应当处理的平面。
每次处理需要先找到左下角的点,然后对当前平面的所有点进行排序,共需要处理n次,所以复杂度O(n^2*logn)。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
typedef long long ll;
using namespace std;
const int N = 2005;
const int M = 24005;
pair<ll,ll>ori;
vector<ll>edg[N];
ll n,m,k;
ll sz[N],ans[N];
struct man{
    ll x,y,id;
    bool operator < (const man & b) const {
        return (x-ori.first)*(b.y-ori.second) - (y-ori.second)*(b.x-ori.first) > 0;
    }
}p[N];
void dfs1(ll u,ll fa){
    sz[u]=1;
    for(int i=0;i<edg[u].size();i++){
        ll v=edg[u][i];
        if(v==fa)continue;
        dfs1(v,u);
        sz[u]+=sz[v];
    }
}
void dfs2(ll u,ll fa,ll s,ll e){
    int pos;
    ll x,y;
    x=y=1e10;
    for(int i=s;i<=e;i++){
        if(p[i].x<x||((p[i].x==x)&&p[i].y<y)){
            x=p[i].x;y=p[i].y;pos=i;
        }
    }
    ori.first=x;ori.second=y;
    swap(p[s],p[pos]);
    sort(p+s+1,p+e+1);
    ans[p[s].id]=u;
    int cnt=0;
    for(int i=0;i<edg[u].size();i++){
        ll v=edg[u][i];
        if(v==fa)continue;
        dfs2(v,u,s+1+cnt,s+1+cnt+sz[v]-1);
        cnt+=sz[v];
    }
}
int main() {
    ll T,u,v;
    scanf("%lld",&n);
    for(int i=1;i<n;i++){
        scanf("%lld%lld",&u,&v);
        edg[u].pb(v);edg[v].pb(u);
    }
    for(int i=0;i<n;i++){
        scanf("%lld%lld",&p[i].x,&p[i].y);
        p[i].id=i;
    }
    dfs1(1,0);
    dfs2(1,0,0,n-1);
    for(int i=0;i<n;i++)printf("%lld ",ans[i]);printf("\n");
    return 0;
}

 

Codeforces Round #124 (Div. 1) C. Paint Tree(极角排序)