海妖沙龙
题目链接:YBT2023寒假Day11 A
题目大意
平面上有 n 个点,然后对于一个排列,如果按顺序走对于的点,会形成若干个线段组成的路径,然后你从前一个线段走到下一个线段端点时候,你需要左转或右转。
然后告诉你走的左转右转序列,要你找一个排列,使得路径两两不交,而且是给出的左转右转序列。
保证有解。
思路
考虑第一条边要怎么选。
看到线段不能相交,而且我们要尽量让下一条边拐向你走的方向。
那如果你选的线段在凸包上,那我们是不是有一个方向可以使得其他点都在你这条边的一测,而且我们可以通过改边的方向,使得拐到他们的方向改变。
那这样的一个好处就是你就不需要管这个边和下一个边的要求,而且这样后面的线段一定不会跟你相交。
那显然我们一直进行下去即可。
那一开始我们选最下最左的一个点,然后每次极角排序即可。
代码
#include<cstdio>
#define ll long long
using namespace std;
const int N = 5050;
struct dian {
ll x, y;
}a[N];
int n, use[N], ans[N];
char S[N];
dian operator -(dian x, dian y) {
return (dian){x.x - y.x, x.y - y.y};
}
ll operator *(dian x, dian y) {
return x.x * y.y - x.y * y.x;
}
int main() {
freopen("route.in", "r", stdin);
freopen("route.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld %lld", &a[i].x, &a[i].y);
}
scanf("%s", S + 1);
int s = 1;
for (int i = 2; i <= n; i++)
if ((a[i].x < a[s].x) || (a[i].x == a[s].x && a[i].y < a[s].y)) s = i;
use[s] = 1;
for (int i = 2; i <= n; i++) {
int t = 0;
for (int j = 1; j <= n; j++)
if (!use[j]) {
if (!t || ((S[i - 1] == 'R') == ((a[j] - a[s]) * (a[t] - a[s]) < 0))) t = j;
}
use[t] = i; s = t;
}
for (int i = 1; i <= n; i++) ans[use[i]] = i;
for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
return 0;
}
标签:dian,int,线段,YBT2023,寒假,Day11,ll
From: https://www.cnblogs.com/Sakura-TJH/p/YBT2023Day11_A.html