【c++】曲线谜题

2023-06-17 02:52| 来源: 网络整理| 查看: 265

题目描述：

果老师在玩一个曲线迷题游戏。

在这个游戏中，有一个 $r\times c$ 的矩形网格，对于整数 $i\left ( 1\leq i \leq N\right )$ 会被填入网格中 $\left ( x_i1{},y_i1{} \right )$ 和 $\left ( x_i2{},y_i2 \right )$ 两个网格。

现在果老师会尝试用曲线连接所有两两相同的数字，使得曲线不会出网格外并且不会交叉。

果老师希望你能帮他判断是否可能。

输入格式：

输出的第一行为三个正整数 $R,C,N$ 。

接下来的 $N$ ，每行四个整数 $x_i1{},y_i1{},x_i2{},y_i2{}$ 。表示 $i$ 填入的网格坐标。

$1\leq R,C\leq 10^{8},1\leq N\leq 10^{5}$

$0\leq x _i1{},x_i2{} \leq R\left ( 1\leq i\leq N\right )$

$0\leq y_i1{},y_i2{}\leq C(1\leq i\leq N)$

给出的坐标点都不重合，所有输入的值都是整数。

输出格式

输入可能输出YES，否则输出NO。

样例输入1

4 2 3 0 1 3 1 1 1 4 1 2 0 2 2

样例输出1

YES

样例输入2

2 2 4 0 0 2 2 2 0 0 1 0 2 1 2 1 1 2 1

样例输出 2

样例输入 3

5 5 7 0 0 2 4 2 3 4 5 3 5 5 2 5 5 5 4 0 3 5 1 2 2 4 4 0 5 4 1

样例输出 3

YES

样例输入 4

1 1 2 0 0 1 1 1 0 0 1

样例输出 4

提示

此题来源于NKOJ P7812

（以下题解仅供学习理解与思路分享，严禁抄袭）

好，那么我们开始

再做这道题之前，我们要明确这个游戏怎么玩

以下给出一个样例

把相同颜色连在一起每两条线相交为一个交叉问最少有几个交叉

在这里大家可以思考一下答案是两的交叉如下图

通过观察我们不难发现两个交叉分别黄色+蓝色褐色+蓝色

三条线都有一个共同点就是两个端点都在边界上

那么我们就可以只看两端点都在边界上的线也就是把图形分成两半的线因为其他线都有一个端点在图中我们就可以绕过端点从而不发生交叉

因为只有两端都在边界上的点才会交叉，那么正方形里面的线就可以不考虑了了这个时候我们把正方形的四边拆开（以下均采用正时针拆开）就能进行降维，从而变成一维图像如下图

如果在一维图中交叉的就一定交叉这里我们可以用排序＋遍历但我介绍一种更简单的方法

我们生成一个栈把生成好的一维数组挨个入栈再在入栈前一个判断如果这个点的编号与栈顶相同那么就删除栈顶元素此元素也不在入栈代表这条线不与其他任何线相交执行完后，如果栈为空则没有交叉反之则有交叉

理论成立，那么实践

首先建立数据结构

struct node{ int x; int y;//x,y均为坐标 int id;//点的编号 int opt;//点在哪条边上 }a[200005];

然后判断点在哪条边上

int get(int x,int y){ if(x==0) return 1;//如果x=0则在上边 if(y==c) return 2;//如果y=c则在右边 if(x==r) return 3;//如果x=r则在下边 if(y==0) return 4;//如果y=0则在左边 }

将两边都在边界上的点存入a数组后再进行拆开

int cmp(node x,node y){//按边排序 if(x.opt==y.opt){//如果在同一边则特殊处理 if(x.opt==1){ return x.yy.x;//从大到小 } } return x.opt

【本文地址】

公司简介

联系我们