「6月雅礼集训 2017 Day8」route

【题目大意】

给出平面上$n$个点，求一条连接$n$个点的不相交的路径，使得转换的方向符合所给长度为$n-2$的字符串。

$n \leq 5000$

【题解】

考虑取凸包上一点，然后如果下一个是‘R'，也就是向右转，那么就连到最左的点，这样下一次无论连到哪里都是向右；如果是'L'，同理。

由于每次都是一个半平面，所以不会相交。

# include <stdio.h>

# include <string.h>

# include <iostream>

# include <algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

const int N = 1e5 + , M = 2e5 + ;

int n;

struct P {

    int x, y;

    P() {}

    P(int x, int y) : x(x), y(y) {}

    friend P operator + (P a, P b) {

        return P(a.x+b.x, a.y+b.y);

    }

    friend P operator - (P a, P b) {

        return P(a.x-b.x, a.y-b.y);

    }

    friend ll operator * (P a, P b) {

        return - 1ll * a.y * b.x + 1ll * a.x * b.y;

    }

    friend ll operator / (P a, P b) {

        return 1ll * a.x * b.x + 1ll * a.y * b.y;

    }

    inline void set() {

        scanf("%d%d", &x, &y);

    }

}p[M];

int ans[M], an;

char str[M];

bool v[M];

int main() {

//    freopen("route.in", "r", stdin);

//    freopen("route.out", "w", stdout);

    cin >> n;

    for (int i=; i<=n; ++i) p[i].set();

    int id = ;

    for (int i=; i<=n; ++i) if(p[i].x > p[id].x) id = i;

    ans[++an] = id; v[id] = ;

    scanf("%s", str+);

    for (int i=; i<=n-; ++i) {

        for (int j=; j<=n; ++j)

            if(!v[j]) {

                id = j;

                break;

            }

        for (int j=id+; j<=n; ++j)

            if(!v[j]) {

                if(((p[id] - p[ans[i]]) * (p[j] - p[ans[i]]) > ) ^ (str[i] == 'L')) id = j;

            }

        ans[++an] = id; v[id] = ;

    }

    for (int i=; i<=n; ++i) if(!v[i]) ans[++an] = i;

    for (int i=; i<=n; ++i) printf("%d ", ans[i]);

    puts("");

    return ;

}