UVa1453/LA4728 Squares

题目链接

         本题是2009年ICPC亚洲区域赛首尔赛区的F题

题意

        给定平面上n个边平行于坐标轴的矩形,在它们的顶点中找出两个欧几里得距离最大的点。如下图所示,距离最大的是S1的左下角和S4的右上角。正方形可以重合或者交叉。
        你的任务是输出这个最大距离的平方。

分析

        首先把矩形的所有顶点求出,得到一个点集,则本题的目标就是要求出这个点集的直径(diameter),即点之间的最大距离。

        这是经典问题:求最远点对。与之对应的另外一个经典问题是最临近点对。

        “寻找最近点对”是用分治策略降低复杂度(并且利用抽屉原理进行分析得出一个跟有趣的结论将时间复杂度优化到O\left ( n\log n \right )),而“寻找最远点对”可利用几何性质将时间复杂度优化到O\left ( n\log n \right )

        注意到对于平面上的n个点,最远点对必然存在于这n个点所构成的一个凸包上(求点集的直径变成了求凸包的直径),那么可以排除大量点,如下图所示:

        找最远点对的枚举方法是旋转卡壳(rotating calipers)法:可以想象有两条平行线, “卡”住这个凸包,然后卡紧的情况下旋转一圈,肯定就能找到凸包直径,也就找到了最远点对。

        细说一下旋转卡壳法:如果qa,qb是凸包上最远两点,必然可以分别过qa,qb画出一对平行线。通过旋转这对平行线,我们可以让它和凸包上的一条边重合,如图中蓝色直线,可以注意到,qa是凸包上离p和qb所在直线最远的点。逆时针枚举凸包上的所有边,对每一条边找出凸包上离该边最远的顶点,计算这个顶点到该边两个端点的距离,并记录最大的值。注意到当逆时针枚举边的时候,最远点的变化也是逆时针的,这样就可以不用从头寻找最远点,而是紧接着上一次的最远点继续寻找,于是得到了O(n)的算法。

        Andrew算法求完“下凸包”时记录下最后一个顶点(即最右的顶点)的索引k,则用k-1作为将来旋转卡壳法枚举凸包首条边时最远顶点即可(实际上首条边的最远顶点k-1)。

AC代码

#include <iostream>
#include <algorithm>
using namespace std;

struct Point {
    int x, y;
    Point(int x = 0, int y = 0): x(x), y(y) {}
};
typedef Point Vector;
 
Vector operator- (const Point& A, const Point& B) {
    return Vector(A.x - B.x, A.y - B.y);
}
 
bool operator< (const Point& a, const Point& b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}
 
bool operator== (const Point& a, const Point& b) {
    return a.x == b.x && a.y == b.y;
}
 
int Cross(const Vector& A, const Vector& B) {
    return A.x * B.y - A.y * B.x;
}

int Dot(const Vector& A, const Vector& B) {
    return A.x * B.x + A.y * B.y;
}

#define N 400040
Point p[N], ch[N];

void solve() {
    int m = 0, n; cin >> n;
    for (int i=0; i<n; ++i) {
        int x, y, w; cin >> x >> y >> w;
        p[4*i] = Point(x, y); p[4*i+1] = Point(x, y+w); p[4*i+2] = Point(x+w, y); p[4*i+3] = Point(x+w, y+w);
    }
    sort(p, p+(n<<=2));
    n = unique(p, p+n) - p;
    for (int i=0; i<n; ++i) {
        while (m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) --m;
        ch[m++] = p[i];
    }
    int k = m;
    for (int i=n-2; i>=0; --i) {
        while (m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) --m;
        ch[m++] = p[i];
    }
    --m;
    int d = 0; Vector v;
    for (int i=0, q=max(k-1, 2); i<m; ++i) {
        while (Cross(v = ch[i+1]-ch[i], ch[q+1]-ch[i]) > Cross(v, ch[q]-ch[i])) q = (q+1) % m;
        d = max(d, max(Dot(v = ch[q]-ch[i], v), Dot(v = ch[q]-ch[i+1], v)));
    }
    cout << d << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/328051.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

P9852 [ICPC2021 Nanjing R] Windblume Festival 题解(SPJ)

[ICPC2021 Nanjing R] Windblume Festival 单击此处下载原神 题面翻译 给一个长度为 n n n 环形整数序列 a a a, 每次操作可以任意选择一个下标 x x x&#xff0c;令 $ a_x a_x - a_{(x\bmod n)1}$&#xff0c;之后移除 a ( x m o d n ) 1 a_{(x\bmod n)1} a(xmodn)1​…

【Linux】Linux 系统编程——which 命令

文章目录 1.命令概述2.命令格式3.常用选项4.相关描述5.参考示例 1.命令概述 which 命令用于定位执行文件的路径。当输入一个命令时&#xff0c;which 会在环境变量 PATH 所指定的路径中搜索每个目录&#xff0c;以查找指定的可执行文件。 2.命令格式 which [选项] 命令名3.常…

华为数通HCIA题库(750题)

完整题库在这里&#xff1a;华为数通HCIA-RS题库注释版-加水印.pdf资源-CSDN文库 此处只节选几题。 1.网络管理员在网络中捕获到了一个数据帧&#xff0c;其目的MAC地址是01-00-5E-AO-B1-C3。关于该MAC地址的说法正确的是&#xff08; )。 A.它是一个单播MAC地址 B.它是一个广播…

【Shell编程练习】编写 shell 脚本,打印 9*9 乘法表

系列文章目录 输出Hello World 通过位置变量创建 Linux 系统账户及密码 监控内存和磁盘容量&#xff0c;小于给定值时报警 猜大小 输入三个数并进行升序排序 编写脚本测试 192.168.4.0/24 整个网段中哪些主机处于开机状态,哪些主机处于关机状态 系列文章目录编写 shell 脚本,打…

【OJ】链表刷题

个人主页 &#xff1a; zxctsclrjjjcph 文章封面来自&#xff1a;艺术家–贤海林 如有转载请先通知 题目 1. 相交链表&#xff08;160&#xff09;1.1 暴力求解1.1.1 分析1.1.2 代码实现 1.2 优化后求解1.2.1 分析1.2.2 代码实现 2. 随机链表的复制&#xff08;138&#xff09;…

个人网站制作 Part 7 添加用户认证和数据库集成 | Web开发项目

文章目录 &#x1f469;‍&#x1f4bb; 基础Web开发练手项目系列&#xff1a;个人网站制作&#x1f680; 用户认证与数据库集成&#x1f528;添加用户认证&#x1f527;步骤 1: 使用Passport.js &#x1f528;集成数据库&#x1f527;步骤 2: 使用MongoDB和Mongoose &#x1f…

48 分布式id的生成策略

1.UUID 1.UUID (Universally Unique Identifier)&#xff0c;通用唯一识别码。UUID是基于当前时间、计数器&#xff08;counter&#xff09;和硬件标识&#xff08;通常为无线网卡的MAC地址&#xff09;等数据计算生成的。UUID由以下几部分的组合&#xff1a; 1.当前日期和时…

Apache Solr <= 8.8.1任意文件读取漏洞复现CVE-2019-17558

一、环境准备 搭建环境vulhub&#xff0c;需要提前安装docker环境 docker安装&#xff1a;docker--安装docker-ce-CSDN博客 vulhub地址&#xff1a;https://github.com/vulhub/vulhub #创建靶场环境 mkdir /opt/vulhub cd /opt/vulhub git https://github.com/vulhub/vulhu…

<软考高项备考>《论文专题 - 71 风险管理(3)》

3 过程2-识别风险 3.1 问题 4W1H过程做什么是识别单个项目风险以及整体项目风险的来源&#xff0c;并记录风险特征的过程。作用:1、记录现有的单个项目风险&#xff0c;以及整体项目风险的来源:2、汇总相关信息&#xff0c;以便项目团队能够恰当地应对已识别的风险。为什么做…

编译原理1.3习题 程序设计语言的发展历程

图源&#xff1a;文心一言 编译原理习题整理~&#x1f95d;&#x1f95d; 作为初学者的我&#xff0c;这些习题主要用于自我巩固。由于是自学&#xff0c;答案难免有误&#xff0c;非常欢迎各位小伙伴指正与讨论&#xff01;&#x1f44f;&#x1f4a1; 第1版&#xff1a;自…

【Java SE语法篇】11.异常

&#x1f4da;博客主页&#xff1a;爱敲代码的小杨. ✨专栏&#xff1a;《Java SE语法》 ❤️感谢大家点赞&#x1f44d;&#x1f3fb;收藏⭐评论✍&#x1f3fb;&#xff0c;您的三连就是我持续更新的动力❤️ 文章目录 1. 异常的概念和体系结构1.1 异常的概念1.2 异常体系…

企业微信开发:自建应用:access_token

access_token 过期后接口响应 access_token 已经过期&#xff08;2小时&#xff09;后&#xff0c;调用接口的响应&#xff1b;本文中以发送消息接口为例&#xff0c;说明接口响应的情况。 官方开发文档链接&#xff1a;获取access_token access_token 过期后调用接口 响应体 …

大模型学习与实践笔记(六)

一、finetune 简介 两种微调模式&#xff1a;增量预训练 与指令跟随 1.增量预训练 2.指令微调 二、LoRA 与 QLoRA 介绍 三、XTuner 介绍 四、低显存玩转LLM的方法

ASP.NET Core 的 Web Api 实现限流 中间件

Microsoft.AspNetCore.RateLimiting 中间件提供速率限制&#xff08;限流&#xff09;中间件。 它是.NET 7 以上版本才支持的中间件&#xff0c;刚看了一下&#xff0c;确实挺好用&#xff0c;下面给大家简单介绍一下&#xff1a; RateLimiterOptionsExtensions 类提供下列用…

【jupyter添加虚拟环境内核(pytorch、tensorflow)- 实操可行】

jupyter添加虚拟环境内核&#xff08;pytorch、tensorflow&#xff09;- 实操可行 1、查看当前状态(winR&#xff0c;cmd进入之后)2、激活虚拟环境并进入3、安装ipykernel5、完整步骤代码总结6、进入jupyter 添加pytorch、tensorflow内核操作相同&#xff0c;以下内容默认已经安…

Python - 深夜数据结构与算法之 Sort

目录 一.引言 二.排序简介 1.排序类型 2.时间复杂度 3.初级排序 4.高级排序 A.快速排序 B.归并排序 C.堆排序 5.特殊排序 三.经典算法实战 1.Quick-Sort 2.Merge-Sort 3.Heap-Sort 4.Relative-Sort-Array [1122] 5.Valid-anagram [242] 6.Merge-Intervals […

idea设置编辑器背景颜色

文章目录 一、Ided常用工具栏显示二、更改idea主题设置三、设置代码编辑器背景颜色为豆沙绿四、设置新项目 默认Jdk配置、maven配置1、settings for new projects2、structre for new projects 五、修改代码中注释的字体颜色六、设置编辑器字体大小七、文件编码的设置(可以设置…

leetcode-344. 反转字符串、9. 回文数

题目1&#xff1a; 解题方法 直接用reverse()即可 代码&#xff1a; class Solution(object):def reverseString(self, s):""":type s: List[str]:rtype: None Do not return anything, modify s in-place instead."""return s.reverse()如果不…

翻译: Pyenv管理Python版本从入门到精通二

Pyenv系列&#xff1a; 翻译: Pyenv管理Python版本从入门到精通一 1. 高级 Pyenv 用法 1.1 在 pyenv-virtualenv 中使用虚拟环境 可以使用 pyenv-virtualenv 扩展 Pyenv 来管理虚拟环境。这是隔离项目环境并有效管理其依赖项的好方法。以下是使用 pyenv-virtualenv 创建虚…

C# 面向切面编程之AspectCore实践(二)

写在前面 在上一篇中对AspectCore进行了初步的了解&#xff0c;用于拦截的属性加在了具体类的方法上。 C# 面向切面编程之AspectCore初探 这一篇验证一下把拦截属性加在接口上&#xff0c;这样实现该接口的类中所对应的方法都会被拦截到&#xff1b;另外示例中还尝试对方法的…