博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU3511 Prison Break 关于圆的扫描线
阅读量:5878 次
发布时间:2019-06-19

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

首先和传统扫描线的方法一样先把每个圆左右侧x坐标离散出来排个序标记好进出,然后开始扫描。

如果全是矩形,就很好处理。圆就麻烦在没有像矩形那样可以离散化的规则上下界,便无法用预处理好的离散编号来构建线段树。

但是我们可以注意到题目中说了圆与圆不会相切或相交,那么对于扫描线扫描的过程中从上到下穿过各个圆的顺序是不会变的,所以可以利用二叉树,把扫描线经过的“边”有序地插入(这里用set就很方便高效了),对于圆来说,这个边就是与上半圆交点纵坐标和与下半圆交点纵坐标。由于扫描线位置的变化,插入时用来比较的代表“边”的纵坐标也会变化,但是前面说过,扫描线穿过圆的顺序是不会变的,所以新的“边”依然会插入到正确的位置,其他“边”的相对位置也不会改变。

边的问题解决了,就可以像矩形的图那样理解了:

扫描到一个矩形A左侧时,上方或下方没有边,则这个矩形在最外侧;

上方与下方边属于同一个矩形B,则矩形A比矩形B深度多1;

上方与下方边分别属于矩形B与矩形C,则矩形A与较深的那个矩形深度相同。

由此可得到每个矩形的深度,更新最深的为答案。

——————————分割线——————————

网上看到有人用随机的做,于是也想试试(有时候就是会做一些无聊的事情……),由于数据没有专门卡随机算法,意外地发现了一个srand()的种子,就93ms了……

——————————分割线——————————

不靠谱的东西就不多说了,只贴个正解的代码。

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 using namespace std; 9 const int maxn = 51111;10 const double eps = 1e-8;11 inline int dcmp(double x) { return (x > eps) - (x < -eps);}12 inline double Sqr(double x) { return x * x;}13 int LineNow, ltp, n, cnt[maxn];14 struct Cir//圆15 {16 int x;17 int y;18 int r;19 }c[maxn];20 struct Line//从左向右扫描节点21 {22 int id;23 bool in;24 void Read(int id_, bool in_){id = id_, in = in_;}25 inline int GetSite()const{ return c[id].x + (in ? -c[id].r : c[id].r);}26 bool operator<(const Line &b)const{ return GetSite() < b.GetSite();}27 }l[maxn << 1];28 struct Node//从上至下排序节点29 {30 int id;31 bool up;32 Node(){}33 Node(int id_, bool up_){id = id_, up = up_;}34 inline double GetSite()const35 { return c[id].y + sqrt(Sqr(c[id].r) - Sqr(LineNow - c[id].x)) * (up ? 1 : -1);}36 bool operator<(const Node &b)const37 {38 double y1 = GetSite();39 double y2 = b.GetSite();40 return dcmp(y1 - y2) ? y1 > y2 : up > b.up;41 }42 };43 set
s;44 set
::iterator iti, itn;45 void ReadData(int n)46 {47 int i;48 for(ltp = i = 0; i < n; ++ i)49 {50 scanf("%d%d%d", &c[i].x, &c[i].y, &c[i].r);51 l[ltp ++].Read(i, true);52 l[ltp ++].Read(i, false);53 }54 }55 int MakeAns()56 {57 int i, ans = 0;58 sort(l, l + ltp);59 s.clear();60 for(i = 0; i < ltp; ++ i)61 {62 LineNow = l[i].GetSite();63 if(!l[i].in)64 {65 s.erase(Node(l[i].id, true));66 s.erase(Node(l[i].id, false));67 }68 else69 {70 iti = itn = s.insert(Node(l[i].id, true)).first;71 itn ++;72 if(iti == s.begin() || itn == s.end()) cnt[l[i].id] = 1;73 else74 {75 iti --;76 if((*iti).id == (*itn).id) cnt[l[i].id] = cnt[(*iti).id] + 1;77 else cnt[l[i].id] = max(cnt[(*iti).id], cnt[(*itn).id]);78 }79 ans = max(ans, cnt[l[i].id]);80 s.insert(Node(l[i].id, false));81 }82 }83 return ans;84 }85 int main()86 {87 while(scanf("%d", &n) != EOF)88 {89 ReadData(n);90 printf("%d\n", MakeAns());91 }92 return 0;93 }

转载于:https://www.cnblogs.com/CSGrandeur/archive/2012/09/12/2681050.html

你可能感兴趣的文章
网页视频流m3u8/ts视频下载
查看>>
【Leetcode】75.颜色分类
查看>>
刷前端面经笔记(十一)
查看>>
几款常见的视频格式转换器
查看>>
使用Data URI Scheme优雅的实现前端导出csv
查看>>
第十七天-企业应用架构模式-会话状态模式
查看>>
Bytom BIP-32协议和BIP-44协议
查看>>
Docker入门(二)在docker使用MongoDB
查看>>
如何抓住下一波零售风口?看RPA玩转零售自动化
查看>>
记一次mpvue开发完整小程序相关笔记
查看>>
三个月可更改用户昵称两次
查看>>
【极简壁纸】简单高效美观的壁纸网站
查看>>
前嗅ForeSpider教程:采集需要登陆的网页内容
查看>>
从现在开始,试着学会用官方文档去学习一个技术框架
查看>>
一篇文章玩转全网音乐信息库MusicBrainz API
查看>>
多功能React影像组件(拖拽、水印、缩放、切换、旋转)
查看>>
springboot+mybatis实现登录功能,返回json
查看>>
python基础总结
查看>>
通过一个例子学习Kubernetes里的PersistentVolumeClaim的用法
查看>>
常见的几种排序方法
查看>>