#include<cstdio>
#include<algorithm>
#define LDB long double
using namespace std; int ans[];
struct lin{
LDB k,b;
int num;
}a[]; struct rec{
LDB inte;
int num;
}sta[]; int mycomp(const lin &a,const lin &b){
if (a.k<b.k) return();
if (a.k>b.k) return();
if (a.b>b.b) return();
return();
} LDB inter(lin a,lin b){
return((b.b-a.b)/(a.k-b.k));
} int main(){
int n;
scanf("%d",&n); for (int i=;i<=n;i++){
int t1,t2;
scanf("%d%d",&t1,&t2);
a[i].k=(LDB)t1;a[i].b=(LDB)t2;a[i].num=i;
} sort(a+,a+n+,mycomp);
int top;
sta[top=].num=;sta[top].inte=-;
for (int i=;i<=n;i++)
if (a[i].k!=a[i-].k){
while ((top>)&&(inter(a[i],a[sta[top].num])<=sta[top].inte)) top--;
sta[++top].num=i;
sta[top].inte=inter(a[i],a[sta[top-].num]);
} for (int i=;i<=top;i++) ans[i]=a[sta[i].num].num;
sort(ans+,ans+top+);
for (int i=;i<=top;i++) printf("%d ",ans[i]);
}
半平面交模板(BZOJ1007)的更多相关文章
-
bzoj 2618 半平面交模板+学习笔记
题目大意 给你n个凸多边形,求多边形的交的面积 分析 题意\(=\)给你一堆边,让你求半平面交的面积 做法 半平面交模板 1.定义半平面为向量的左侧 2.将所有向量的起点放到一个中心,以中心参照进行逆 ...
-
POJ 3525 /// 半平面交 模板
题目大意: 给定n,接下来n行逆时针给定小岛的n个顶点 输出岛内离海最远的点与海的距离 半平面交模板题 将整个小岛视为由许多半平面围成 那么以相同的比例缩小这些半平面 一直到缩小到一个点时 那个点就是 ...
-
半平面交模板(O(n*n)&;&; O(n*log(n))
摘自http://blog.csdn.net/accry/article/details/6070621 首先解决问题:什么是半平面? 顾名思义,半平面就是指平面的一半,我们知道,一条直线可以将平面分 ...
-
POJ 半平面交 模板题 三枚
给出三个半平面交的裸题. 不会的上百度上谷(gu)歌(gou)一下. 毕竟学长的语文是体育老师教的.(卡格玩笑,别当真.) 这种东西明白就好,代码可以当模板. //poj1474 Video Surv ...
-
再来一道测半平面交模板题 Poj1279 Art Gallery
地址:http://poj.org/problem?id=1279 题目: Art Gallery Time Limit: 1000MS Memory Limit: 10000K Total Su ...
-
bzoj 2618【半平面交模板】
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> usin ...
-
【BZOJ 2618】 2618: [Cqoi2006]凸多边形 (半平面交)
2618: [Cqoi2006]凸多边形 Description 逆时针给出n个凸多边形的顶点坐标,求它们交的面积.例如n=2时,两个凸多边形如下图: 则相交部分的面积为5.233. Input 第一 ...
-
POJ3335 POJ3130 POJ1474 [半平面交]
终于写出自己的半平面交模板了....... 加入交点的地方用了直线线段相交判定 三个题一样,能从任何地方看到就是多边形的内核 只不过一个顺时针一个逆时针(给出一个多边形的两种方式啦),反正那个CutP ...
-
Harry Potter and J.K.Rowling(半平面交+圆和矩形交)
Harry Potter and J.K.Rowling http://acm.hdu.edu.cn/showproblem.php?pid=3982 Time Limit: 2000/1000 MS ...
随机推荐
-
Android各类权限意思祥解
1. android.permission.ACCESS_CHECKIN_PROPERTIES 允许读写访问”properties”表在 checkin数据库中,可以修改值上传 2. andro ...
-
UltraEdit 注册机使用说明
请断开网络连接(或直接拔掉网线)后执行: 安装完成后,点击弹出界面的“注册”按钮,然后直接点击“激活”,此时UltraEdit检测到网络断开则弹出界面提示“脱机激活”,此时启动注册机,并将UltraE ...
-
离线更新VSAN HCL数据库
从VSAN 6.0起,VSAN提供了Health Check功能,其中就包括VSAN HCL数据库,通过此运行状况检查验证用于 HCL 检查的 VMware 兼容性指南数据库是否是最新的.这些 VCG ...
-
理解并使用.NET 4.5中的HttpClient
HttpClient介绍 HttpClient是.NET4.5引入的一个HTTP客户端库,其命名空间为System.Net.Http..NET 4.5之前我们可能使用WebClient和HttpWeb ...
-
最火的Android开源项目整理
一.代码库 1.from 代码家 整理比较好的源码连接 ******************************************************************* ...
-
IDA*
模拟退火 基本思路(Main Thoughts): IDA*是一种优秀的搜索法,在一般的实际问题中,它比普通的搜索更快. 通过迭代加深和估价函数剪枝来搜索. 通常处理没有层数上界或上界很多大的搜索. ...
-
构造数组的MaxTree
题目 一个数组的MaxTree定义: 数组必须没有重复元素 MaxTree是一棵二叉树,数组的每一个值对应一个二叉树节点 包括MaxTree树在内且在其中的每一棵子树上,值最大的节点都是树的头 给定一 ...
-
hdoj 1251 字典树||map
统计难题 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others)Total Submi ...
-
web前端研发工程师编程能力成长之路
[背景] 如果你是刚进入WEB前端研发领域,想试试这潭水有多深,看这篇文章吧:如果你是做了两三年WEB产品前端研发,迷茫找不着提高之路,看这篇文章吧:如果你是四五年的前端开发高手,没有难题能难得住你的 ...
-
Http的定义及其基本概念介绍
HTTP的特性 HTTP构建于TCP/IP协议之上,默认端口号是80 HTTP是无连接无状态的 HTTP报文 请求报文 HTTP定义了与服务器交互的不同方法,最基本的方法有4种,分别是GET,POST ...