首页 > 其他分享 >【YBT2023寒假Day11 A】海妖沙龙(计算几何)

【YBT2023寒假Day11 A】海妖沙龙(计算几何)

时间:2023-02-21 00:34:12浏览次数:54  
标签:dian int 线段 YBT2023 寒假 Day11 ll

海妖沙龙

题目链接: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

相关文章

  • H - 线段树 1【GDUT_22级寒假训练专题五】
    H-线段树1原题链接题意区间修改区间查询线段树简介线段树是一颗二叉树,他能通过树的分支将一块区间划分为数个单元区间,每个单元区间对应线段树中的一个叶结点。如......
  • 【YBT2023寒假Day10 C】娄居吉勾(点分树)
    娄居吉勾题目链接:YBT2023寒假Day10C题目大意有一个n个点m条边的无向连通图,每个点至多在k个简单环上。然后有q个操作,标记一个没有标记过的点,或者给你一个点求......
  • 寒假训练第四周
      题目大意意思就是给一个n和一个kk是2的k次方n是分子在2的k次方上面从1到n分子依次加一然后要进行分数有理化然后把有理化的分子相加即可思路因为是2的k次方......
  • 寒假学习记录(三)
    这个作业属于哪个课程<班级的链接>这个作业要求在哪里<作业要求的链接>这个作业的目标学有所得一、写在前面对于每次寒假作业的目标,我给自己设定的都......
  • 【YBT2023寒假Day10 B】随机游走(记忆化搜索)
    随机游走题目链接:YBT2023寒假Day10B题目大意有n个点排成环,你一开始在1号点,每次可以等概率选择左边跳两格,左边跳一格,右边跳一格,右边跳两格。走到一个走过的点就停......
  • 【YBT2023寒假Day10 A】集合比较(数学)(启发式分裂)
    集合比较题目链接:YBT2023寒假Day10A题目大意给你一个长度为n的排列p,定义两个大小为n不可重集合的比较方式是先比较各自第p1小的元素,如果相同比p2,以此类推。给......
  • 寒假学习总结
    这个作业属于哪个课程班级这个作业要求在哪里作业的要求这个作业的目标对寒假学习的总结寒假学习总结一、回顾在本次寒假的学习当中,收益颇丰,每次作业......
  • 寒假训练第六周
    寒假训练第六周第一天蓝桥杯训练斐波拉契数组大意:给定数组A,为最少修改几个元素后,数组A会变成一个斐波拉契数组。思路:斐波那契数组在第 30 项左右就超过 1e6了。......
  • B - Fedya and Maths 【GDUT_22级寒假训练专题五】
    B-FedyaandMaths原题链接思路找到规律发现答案以4为周期循环如果被4整除那么答案则为4,否则答案为0疑难一个长度为\(10^5\)的数怎么对4进行取模运算?分别取模如:......
  • 寒假学习记录
    这个作业属于哪个课程<班级链接>这个作业要求在哪里 <作业要求>这个作业的目标<寒假学习记录>一、对寒假的回顾尚可的点:首先在完成了在结束六级一轮......