博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
半平面交模板(BZOJ1007)
阅读量:6818 次
发布时间:2019-06-26

本文共 1113 字,大约阅读时间需要 3 分钟。

#include
#include
#define LDB long doubleusing namespace std; int ans[600000]; struct lin{ LDB k,b; int num; }a[600000]; struct rec{ LDB inte; int num; }sta[600000]; int mycomp(const lin &a,const lin &b){ if (a.k
b.k) return(0); if (a.b>b.b) return(1); return(0); } 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=1;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+1,a+n+1,mycomp); int top; sta[top=1].num=1;sta[top].inte=-1000000000; for (int i=2;i<=n;i++) if (a[i].k!=a[i-1].k){ while ((top>0)&&(inter(a[i],a[sta[top].num])<=sta[top].inte)) top--; sta[++top].num=i; sta[top].inte=inter(a[i],a[sta[top-1].num]); } for (int i=1;i<=top;i++) ans[i]=a[sta[i].num].num; sort(ans+0,ans+top+1); for (int i=1;i<=top;i++) printf("%d ",ans[i]); }

 

转载于:https://www.cnblogs.com/zhujiangning/p/5594478.html

你可能感兴趣的文章
python转换文本编码和windows换行符
查看>>
try-catch中导致全局变量无法变化的bug
查看>>
Js中数组的操作
查看>>
浏览器缓存 from memory cache与from disk cache详解
查看>>
php编译常用选项
查看>>
Docker Machine 简介
查看>>
Angular4错误提示的说明(一)
查看>>
CCNA+NP学习笔记—交换网络篇
查看>>
一张图说明Linux启动过程
查看>>
Provider处理请求逻辑梳理
查看>>
我的友情链接
查看>>
查看当前服务链接数
查看>>
Open-Falcon 互联网企业级监控系统解决方案(2)
查看>>
抄录一份linux哲学思想
查看>>
DBLIKE创建命令
查看>>
cesiumjs开发实践(五) 坐标变换
查看>>
明明白白学C#第0章准备工作
查看>>
Xamarin.Forms单元控件Cell
查看>>
Linux下MySQL备份以及crontab定时备份
查看>>
Exchange 2016和 O365 混合部署系列三之混合配置
查看>>