热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

BZOJ1007.[HNOI2008]水平可见直线

可见的直线为一下凸壳。先按斜率和截距从小到大排序,再用单调栈判断交点的相对位置即可。#includeconstintN5e4+7;constdouble

可见的直线为一下凸壳。

先按斜率和截距从小到大排序,再用单调栈判断交点的相对位置即可。


#include
const int N = 5e4 + 7;
const double eps = 1e-7;
inline int dcmp(double x) {
if (fabs(x) return x <0 ? -1 : 1;
}
struct P {
double x, y;
int id;
inline bool operator <(const P &rhs) const {
if (dcmp(x - rhs.x) == 0) return y return x }
} p[N];
int st[N], top;
inline double crossx(const P &a, const P &b) {
return (a.y - b.y) / (b.x - a.x);
}
void ins(int id) {
const P &cur = p[id];
while (top) {
if (dcmp(p[st[top]].x - cur.x) == 0) top--;
else if (top > 1 && dcmp(crossx(p[st[top]], cur) - crossx(p[st[top]], p[st[top - 1]])) <= 0) top--;
else break;
}
st[++top] = id;
}
int ans[N];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lf%lf", &p[i].x, &p[i].y);
p[i].id = i;
}
std::sort(p + 1, p + 1 + n);
for (int i = 1; i <= n; i++)
ins(i);
for (int i = 1; i <= top; i++)
ans[p[st[i]].id] = 1;
for (int i = 1; i <= n; i++)
if (ans[i])
printf("%d ", i);
return 0;
}
View Code

推荐阅读
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]
  • Linux设备驱动程序:异步时间操作与调度机制
    本文介绍了Linux内核中的几种异步延迟操作方法,包括内核定时器、tasklet机制和工作队列。这些机制允许在未来的某个时间点执行任务,而无需阻塞当前线程,从而提高系统的响应性和效率。 ... [详细]
  • Codeforces Round #566 (Div. 2) A~F个人题解
    Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意:给你一个的表格,你 ... [详细]
  • 在多线程编程环境中,线程之间共享全局变量可能导致数据竞争和不一致性。为了解决这一问题,Linux提供了线程局部存储(TLS),使每个线程可以拥有独立的变量副本,确保线程间的数据隔离与安全。 ... [详细]
  • 本文介绍如何使用Objective-C结合dispatch库进行并发编程,以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码,展示dispatch库的强大功能。 ... [详细]
  • C++: 实现基于类的四面体体积计算
    本文介绍如何使用C++编程语言,通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式,并提供了两种不同的实现方式。 ... [详细]
  • 本文探讨了如何在模运算下高效计算组合数C(n, m),并详细介绍了乘法逆元的应用。通过扩展欧几里得算法求解乘法逆元,从而实现除法取余的计算。 ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
  • 文件描述符、文件句柄与打开文件之间的关联解析
    本文详细探讨了文件描述符、文件句柄和打开文件之间的关系,通过具体示例解释了它们在操作系统中的作用及其相互影响。 ... [详细]
  • 本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法,包括具体的实现代码和运行示例。通过这些内容,读者可以更好地理解和掌握链表的基本操作。 ... [详细]
  • 本题涉及一棵由N个节点组成的树(共有N-1条边),初始时所有节点均为白色。题目要求处理两种操作:一是改变某个节点的颜色(从白变黑或从黑变白);二是查询从根节点到指定节点路径上的第一个黑色节点,若无则输出-1。 ... [详细]
  • 本文探讨了《魔兽世界》中红蓝两方阵营在备战阶段的策略与实现方法,通过代码展示了双方如何根据资源和兵种特性进行战士生产。 ... [详细]
  • 本题通过将每个矩形视为一个节点,根据其相对位置构建拓扑图,并利用深度优先搜索(DFS)或状态压缩动态规划(DP)求解最小涂色次数。本文详细解析了该问题的建模思路与算法实现。 ... [详细]
author-avatar
川人是天下的盐恋歌_334
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有