半平面交模板(BZOJ1007)

时间:2022-09-26 10:22:11
#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)的更多相关文章

  1. bzoj 2618 半平面交模板&plus;学习笔记

    题目大意 给你n个凸多边形,求多边形的交的面积 分析 题意\(=\)给你一堆边,让你求半平面交的面积 做法 半平面交模板 1.定义半平面为向量的左侧 2.将所有向量的起点放到一个中心,以中心参照进行逆 ...

  2. POJ 3525 &sol;&sol;&sol; 半平面交 模板

    题目大意: 给定n,接下来n行逆时针给定小岛的n个顶点 输出岛内离海最远的点与海的距离 半平面交模板题 将整个小岛视为由许多半平面围成 那么以相同的比例缩小这些半平面 一直到缩小到一个点时 那个点就是 ...

  3. 半平面交模板(O(n&ast;n)&amp&semi;&amp&semi; O&lpar;n&ast;log&lpar;n&rpar;)

    摘自http://blog.csdn.net/accry/article/details/6070621 首先解决问题:什么是半平面? 顾名思义,半平面就是指平面的一半,我们知道,一条直线可以将平面分 ...

  4. POJ 半平面交 模板题 三枚

    给出三个半平面交的裸题. 不会的上百度上谷(gu)歌(gou)一下. 毕竟学长的语文是体育老师教的.(卡格玩笑,别当真.) 这种东西明白就好,代码可以当模板. //poj1474 Video Surv ...

  5. 再来一道测半平面交模板题 Poj1279 Art Gallery

    地址:http://poj.org/problem?id=1279 题目: Art Gallery Time Limit: 1000MS   Memory Limit: 10000K Total Su ...

  6. bzoj 2618【半平面交模板】

    #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> usin ...

  7. 【BZOJ 2618】 2618&colon; &lbrack;Cqoi2006&rsqb;凸多边形 (半平面交)

    2618: [Cqoi2006]凸多边形 Description 逆时针给出n个凸多边形的顶点坐标,求它们交的面积.例如n=2时,两个凸多边形如下图: 则相交部分的面积为5.233. Input 第一 ...

  8. POJ3335 POJ3130 POJ1474 &lbrack;半平面交&rsqb;

    终于写出自己的半平面交模板了....... 加入交点的地方用了直线线段相交判定 三个题一样,能从任何地方看到就是多边形的内核 只不过一个顺时针一个逆时针(给出一个多边形的两种方式啦),反正那个CutP ...

  9. Harry Potter and J&period;K&period;Rowling&lpar;半平面交&plus;圆和矩形交&rpar;

    Harry Potter and J.K.Rowling http://acm.hdu.edu.cn/showproblem.php?pid=3982 Time Limit: 2000/1000 MS ...

随机推荐

  1. Android各类权限意思祥解

    1. android.permission.ACCESS_CHECKIN_PROPERTIES    允许读写访问”properties”表在 checkin数据库中,可以修改值上传 2. andro ...

  2. UltraEdit 注册机使用说明

    请断开网络连接(或直接拔掉网线)后执行: 安装完成后,点击弹出界面的“注册”按钮,然后直接点击“激活”,此时UltraEdit检测到网络断开则弹出界面提示“脱机激活”,此时启动注册机,并将UltraE ...

  3. 离线更新VSAN HCL数据库

    从VSAN 6.0起,VSAN提供了Health Check功能,其中就包括VSAN HCL数据库,通过此运行状况检查验证用于 HCL 检查的 VMware 兼容性指南数据库是否是最新的.这些 VCG ...

  4. 理解并使用&period;NET 4&period;5中的HttpClient

    HttpClient介绍 HttpClient是.NET4.5引入的一个HTTP客户端库,其命名空间为System.Net.Http..NET 4.5之前我们可能使用WebClient和HttpWeb ...

  5. 最火的Android开源项目整理

    一.代码库   1.from  代码家 整理比较好的源码连接   ******************************************************************* ...

  6. IDA&ast;

    模拟退火 基本思路(Main Thoughts): IDA*是一种优秀的搜索法,在一般的实际问题中,它比普通的搜索更快. 通过迭代加深和估价函数剪枝来搜索. 通常处理没有层数上界或上界很多大的搜索. ...

  7. 构造数组的MaxTree

    题目 一个数组的MaxTree定义: 数组必须没有重复元素 MaxTree是一棵二叉树,数组的每一个值对应一个二叉树节点 包括MaxTree树在内且在其中的每一棵子树上,值最大的节点都是树的头 给定一 ...

  8. hdoj 1251 字典树&vert;&vert;map

    统计难题 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131070/65535 K (Java/Others)Total Submi ...

  9. web前端研发工程师编程能力成长之路

    [背景] 如果你是刚进入WEB前端研发领域,想试试这潭水有多深,看这篇文章吧:如果你是做了两三年WEB产品前端研发,迷茫找不着提高之路,看这篇文章吧:如果你是四五年的前端开发高手,没有难题能难得住你的 ...

  10. Http的定义及其基本概念介绍

    HTTP的特性 HTTP构建于TCP/IP协议之上,默认端口号是80 HTTP是无连接无状态的 HTTP报文 请求报文 HTTP定义了与服务器交互的不同方法,最基本的方法有4种,分别是GET,POST ...