博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj3067
阅读量:6124 次
发布时间:2019-06-21

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

求交点的个数;

容易发现,对于两条航线(xi,yi)和(xj,yj),设xi<xj

只有yi>yj时两条航线存在交点;

于是我们考虑以x为第一关键字减序,y为第二关键字为减序排序;

则对于当前航线(xi,yi),只要找之前所有yj小于yi的个数

所有交点数就是其总和,统计就要用到飘逸的树状数组了~

1 var a,c:array[0..1010] of longint; 2     x,y:array[0..1000010] of longint; 3     i,j,n,m,k,t:longint; 4     ans:int64; 5  6 procedure add(p:longint); 7   begin 8     while p<=m do 9     begin10       inc(c[p]);11       p:=p+lowbit(p);12     end;13   end;14 function ask(p:longint):longint;15   begin16     ask:=0;17     while p<>0 do18     begin19       ask:=ask+c[p];20       p:=p-lowbit(p);21     end;22   end;23 procedure sort(l,r: longint);24   var i,j,h,p: longint;25   begin26     i:=l;27     j:=r;28     h:=x[(l+r) div 2];29     p:=y[(l+r) div 2];30     repeat31       while (x[i]
j) then34       begin35         swap(x[i],x[j]);36         swap(y[i],y[j]);37         inc(i);38         j:=j-1;39       end;40     until i>j;41     if l
View Code

 

转载于:https://www.cnblogs.com/phile/p/4473301.html

你可能感兴趣的文章
linux:yum和apt-get的区别
查看>>
Sentinel 1.5.0 正式发布,引入 Reactive 支持
查看>>
如何对网站进行归档
查看>>
数据库之MySQL
查看>>
2019/1/15 批量删除数据库相关数据
查看>>
数据类型的一些方法
查看>>
Mindjet MindManager 2019使用教程:
查看>>
游戏设计的基本构成要素有哪些?
查看>>
详解 CSS 绝对定位
查看>>
AOP
查看>>
我的友情链接
查看>>
NGUI Label Color Code
查看>>
.NET Core微服务之基于Polly+AspectCore实现熔断与降级机制
查看>>
vue组件开发练习--焦点图切换
查看>>
浅谈OSI七层模型
查看>>
Webpack 2 中一些常见的优化措施
查看>>
移动端响应式
查看>>
python实现牛顿法求解求解最小值(包括拟牛顿法)【最优化课程笔记】
查看>>
js中var、let、const的区别
查看>>
腾讯云加入LoRa联盟成为发起成员,加速推动物联网到智联网的进化
查看>>