IOI2020集训队作业-1 (CF549E, CF674G, ARC103F)

2023-10-17 20:50

本文主要是介绍IOI2020集训队作业-1 (CF549E, CF674G, ARC103F),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

A - CF549E Sasha Circle

题意

平面内有两个点集 N , M N,M N,M,问能否在平面内画一个圆,使得 N N N M M M这两个点集恰好有一个点集所有点严格在圆内,另一个点集所有点严格在圆外(即两个点集都不能有点在圆上)。

坐标为 [ − 1 0 4 , 1 0 4 ] [-10^4,10^4] [104,104]的整数, ∣ N ∣ , ∣ M ∣ ≤ 1 0 4 |N|,|M|\le 10^4 N,M104

Sol

朴素算法

枚举哪个集合在圆内,假设在圆内的集合是 A A A,在圆外的集合是 B B B

枚举 A A A中的两个点 p , q p,q p,q,令圆过这两个点,则只需要再知道圆心就可以确定圆。考虑剩下的点,“限制某个点在圆内/圆外”可以转化成对圆心的限制,最后圆心可能取的位置一定是 p q pq pq中垂线上的一条线段。由于这道题要求点和圆不能交,所以取值范围的线段的端点不能够重合。容易发现,当取值范围的线段端点没有重合的时候,我们通过一定的调整就可以使得圆不经过 p , q p,q p,q

这样做的复杂度是 O ( ∣ A ∣ 2 ⋅ ( ∣ A ∣ + ∣ B ∣ ) ) O( |A|^2 \cdot (|A| + |B|)) O(A2(A+B))的。

优化

把这个问题放到三维坐标系中,原来的点在 x O y xOy xOy这个平面上。

考虑 x 2 + y 2 = z x^2 +y^2 = z x2+y2=z这个曲面,把 A , B A,B A,B这两个点集中的点垂直于 x O y xOy xOy地投影到这个曲面上得到点集 A ′ , B ′ A',B' A,B。考虑任意一个不与 x O y xOy xOy垂直的平面 a x + b y + z = c ax + by + z =c ax+by+z=c,与曲面的解析式联立可以得到 x 2 + a x + y 2 + b y = c x^2+ax+y^2+by=c x2+ax+y2+by=c,这是圆方程的形式。所以,曲面 z = x 2 + y 2 z = x^2 + y^2 z=x2+y2与任意一个不垂直于 x O y xOy xOy的平面的交集,垂直投影到平面 x O y xOy xOy上,得到的一定是一个圆;一个曲面上的点投影到 x O y xOy xOy之后在圆内,当且仅当在曲面上它在那个平面的下方。

所以,问题转化成判断能否找出一个不垂直于 x O y xOy xOy的平面, A ′ A' A所有点都在平面的下方, B ′ B' B所有点都在平面的上方。

显然只有 A ′ A' A的上凸壳的这些平面是有用的。

由于曲面 z = x 2 + y 2 z = x^2 + y^2 z=x2+y2是向下凸的,所以 A ′ A' A上凸壳顶点的点的投影一定是 A A A的凸包端点。

而上凸壳上的某一个平面,它与这个曲面的交在 x O y xOy xOy上的投影,实际上是平面在 x O y xOy xOy上的投影的外接圆。也就是说,上凸壳上的每一个多边形在 x O y xOy xOy的投影都满足:1)所有端点共圆;2)外接圆都包含了 A A A中的所有点。

如图所示(官方题解里的图):

1-1.png

故而我们可以:将 A A A的凸包划分成若干个三角形,使得每一个三角形的外接圆都包含 A A A中的所有点,然后对三角形上的每一条边进行前面的朴素算法。

由于三维中的上凸壳是存在且唯一的,所以这样的划分方式一定存在,并且当 A A A没有四点共圆的时候是唯一的。

这种三角剖分称为Anti-Delaunay Triagulation。

求出三角剖分之后计算答案的复杂度是 O ( C 2 3 ( ∣ N ∣ + ∣ M ∣ ) ) O (C^{2\over 3}(|N|+|M|)) O(C32(N+M))(其中 C C C是坐标绝对值大小, C 2 3 C^{2\over 3} C32是凸包点数的最大值),可以接受。

现在还剩下的问题是如何在 O ( ( C 2 3 ) 2 ) O((C^{2\over 3})^2) O((C32)2)以下的时间复杂度内求出三角剖分。

求一个凸多边形的Anti-Delaunay Triagulation

首先随便选择多边形的一条边 p 1 p 2 p_1p_2 p1p2,然后找出多边形上的另一个端点 p k p_k pk使得 p 1 , p 2 , p k p_1,p_2,p_k p1,p2,pk确定圆的半径最大。由于凸多边形的三角剖分一定存在,所以这个外接圆一定包含凸多边形的所有端点;又因为当没有四点共圆的情况的时候三角剖分唯一,所以这个多边形的三角剖分中一定有 △ p 1 p 2 p k \triangle p_1p_2p_k p1p2pk。这样我们就将原问题转化成了由 p 1 p k p_1p_k p1pk p 2 p k p_2p_k p2pk划开的两个规模更小的子问题,递归求解即可。

设多边形的端点数为 n n n,则复杂度 O ( n 2 ) O(n^2) O(n2)

实现细节

  • 在进行那个朴素算法的时候,首先没有必要去算圆心 o o o,因为我们只需要确定从 o p ⃗ \vec{op} op o q ⃗ \vec{oq} oq 的角的大小就可以了。而这个角的大小等于圆上的第三个点与 p , q p,q p,q的夹角的二分之一。所以我们只需要考虑 A , B A,B A,B中的其它点与 p , q p,q p,q的夹角带来的限制就可以了。而比较角的大小这里用比较余切值的大小比较方便,只需要特殊考虑点与 p q pq pq贡献的情况。
    假设我们现在在检查的点是 u u u ∠ p u q = α , ∠ p o q = β \angle puq = \alpha,\angle poq=\beta puq=α,poq=β,注意这里角的大小是带符号的。

    • 要求 u u u在圆内:

      • p u ⃗ \vec{pu} pu p q ⃗ \vec{pq} pq 的逆时针方向:那么则要求 cot ⁡ β > cot ⁡

这篇关于IOI2020集训队作业-1 (CF549E, CF674G, ARC103F)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/227878

相关文章

作业提交过程之HDFSMapReduce

作业提交全过程详解 (1)作业提交 第1步:Client调用job.waitForCompletion方法,向整个集群提交MapReduce作业。 第2步:Client向RM申请一个作业id。 第3步:RM给Client返回该job资源的提交路径和作业id。 第4步:Client提交jar包、切片信息和配置文件到指定的资源提交路径。 第5步:Client提交完资源后,向RM申请运行MrAp

Java高级Day38-网络编程作业

112.网络编程作业 //1.使用字符流的方式,编写一个客户端程序和服务器端程序//2.客户端发送"name",服务器端接收到后,返回"我是nova"//3.客户端发送"hobby",服务器端接收到后,返回"编写java程序"//4.不是这两个问题,回复"你说啥呢"​​===============//客户端//===============public class SocketT

0906作业+思维导图梳理

一、作业: 1、创捷一个类似于qq登录的界面 1)源代码 #include "widget.h"#include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget){ui->setupUi(this);//QPushbutton:登录、退出this->join = new QP

2024.9.6 作业

1> 手写unique_ptr指针指针 #include <iostream>using namespace std;template <typename T>class my_unique_ptr{public:explicit my_unique_ptr(T *p = nullptr) noexcept // 构造函数{ptr = p;}~my_unique_ptr() noexcep

9月6号作业

1:.h文件 #ifndef MAINWINDOW_H #define MAINWINDOW_H #include <QMainWindow> #include <QWidget> #include<QIcon> //图标类 #include<QLabel> //标签类 #include<QMovie> //动图类 #include<QLineEdit> //行编辑器类

Flink实例(六十九): flink 作业提交(四)总结

独立集群提交 # 启动集群bin/start-cluster.sh# 提交job./bin/flink run ./examples/batch/WordCount.jar --input hdfs:/user/yuan/input/wc.count --output hdfs:/user/yuan/swwwttt yarn session # 启动集群./bin/

【#第三期实战营闯关作业 ## 茴香豆:企业级知识库问答工具】

今天学习了《 茴香豆:企业级知识库问答工具》这一课,对大模型的应用有了更深得认识。以下是记录本课实操过程及截图: 搭建茴香豆虚拟环境: 输入以下命令 ``studio-conda -o internlm-base -t huixiangdou 成功安装虚拟环境截图 安装茴香豆 cd /root 克隆代码仓库 git clone https://github.com/internlm/h

Quartz 作业调度器

1、Quartz  java实现  注:这里使用的是Quartz1.6.5版本(包:quartz-1.6.5.jar)   [java]  view plain copy //测试main函数   //QuartzTest.java   package quartzPackage;         import java.text.SimpleDateFormat

清华MEM作业-利用管理运筹学的分析工具slover求解最优解的实现 及 通过使用文件或者套节字来识别进程的fuser命令

一、清华MEM作业-利用管理运筹学的分析工具slover求解最优解的实现         最近又接触了一些线性求解的问题,以前主要都是在高中数学里接触到,都是使用笔算,最后通过一些函数式得出最小或者最大值,最近的研究生学业上接触到了一个Excel solver分析工具,对这种线性求最优解的问题感觉使用起来真是得心应手。在使用这个工具前,EXCEL里需要先装上solver工具,装起来很也简单,网上

opencv作业

作业下载地址: 链接:http://pan.baidu.com/s/1qYQnbkw 密码:v7y9