• 离大海最远点在哪里?

    离大海最远点在哪里?

    http://218.5.5.242:9014/problem.asp?id=1678题目描述遥远的海上有一座岛屿,这个岛屿的轮廓是一个凸多边形,把边视为岛屿的海岸线。当地的居民想要在岛屿上找一地点使其到大海的距离最远,这地点应在哪里?岛上居民们习惯地把岛上某个点到岛屿的各条海岸线(即各边)距离中最小者看成该点到大海的距离。如下图所示,点O到大海的距离为min{j,k,l,m,n}=j,其中j,k,l,m,n分别为O到AB,BC,CD,DE,EA的距离。现在,给您N...

    02015年2月3日1,940STL,链表,二分法,半平面交
  • 【poj2187】Beauty Contest

    【poj2187】Beauty Contest

    DescriptionBessie,FarmerJohn'sprizecow,hasjustwonfirstplaceinabovinebeautycontest,earningthetitle'MissCowWorld'.Asaresult,BessiewillmakeatourofN(2<=N<=50,000)farmsaroundtheworldinordertospreadgoodwillbetweenfarmersandtheircows.Forsimplicity,theworldwillberepresentedasatwo-dimensionalplane,whereeachfarmislocatedatapairofintegercoordinates(x,y),eachhavingavalueintherange-10,000...1...

    12015年1月25日3,196凸包,旋转卡壳
  • 【bzoj2823】[AHOI2012]信号塔

    【bzoj2823】[AHOI2012]信号塔

    Description在野外训练中,为了确保每位参加集训的成员安全,实时的掌握和收集周边环境和队员信息非常重要,集训队采用的方式是在训练所在地散布N个小型传感器来收集并传递信息,这些传感器只与设在集训地中的信号塔进行通信,信号塔接收信号的覆盖范围是圆形,可以接收到所有分布在该集训区域内所有N个小型传感器(包括在该圆形的边上)发出的信号。信号塔的功率与信号塔接收范围半径的大小成正比,因为是野外训练,只能使用事...

    02014年12月29日2,036几何,随机化
  • 【bzoj3190】[JLOI2013]赛车

    【bzoj3190】[JLOI2013]赛车

    Description这里有一辆赛车比赛正在进行,赛场上一共有N辆车,分别称为个g1,g2……gn。赛道是一条无限长的直线。最初,gi位于距离起跑线前进ki的位置。比赛开始后,车辆gi将会以vi单位每秒的恒定速度行驶。在这个比赛过程中,如果一辆赛车曾经处于领跑位置的话(即没有其他的赛车跑在他的前面),这辆赛车最后就可以得奖,而且比赛过程中不用担心相撞的问题。现在给出所有赛车的起始位置和速度,你的任务就是算出那些赛车将会得...

    42014年12月25日2,372半平面交
  • 【bzoj1185】[HNOI2007]最小矩形覆盖

    【bzoj1185】[HNOI2007]最小矩形覆盖

    Description题解首先有一个结论,矩形的一条边一定在凸包上!!!枚举凸包上的边用旋转卡壳在凸包上找矩形另外三点。。。注意精度问题[crayon-599511fb528c2804025887/]  ...

    72014年12月24日3,172凸包,旋转卡壳
  • 【bzoj1822】 [JSOI2010]Frozen Nova 冷冻波

    【bzoj1822】 [JSOI2010]Frozen Nova 冷冻波

    DescriptionWJJ喜欢“魔兽争霸”这个游戏。在游戏中,巫妖是一种强大的英雄,它的技能FrozenNova每次可以杀死一个小精灵。我们认为,巫妖和小精灵都可以看成是平面上的点。当巫妖和小精灵之间的直线距离不超过R,且巫妖看到小精灵的视线没有被树木阻挡(也就是说,巫妖和小精灵的连线与任何树木都没有公共点)的话,巫妖就可以瞬间杀灭一个小精灵。在森林里有N个巫妖,每个巫妖释放FrozenNova之后,都需要等待一段时间,...

    62014年12月15日1,928最大流,二分法,几何
  • 【bzoj1027】[JSOI2007]合金

    【bzoj1027】[JSOI2007]合金

    Description某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料,不同种类的原材料中铁铝锡的比重不同。然后,将每种原材料取出一定量,经过融解、混合,得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。现在,用户给出了n种他们需要的合金,以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料,并且使用这些原材料可以加工出用户需要的所有种类的合金。Input第一行两个...

    72014年12月9日3,067floyd,几何
  • 【bzoj2732】[HNOI2012]射箭

    【bzoj2732】[HNOI2012]射箭

    Description沫沫最近在玩一个二维的射箭游戏,如下图1所示,这个游戏中的x轴在地面,第一象限中有一些竖直线段作为靶子,任意两个靶子都没有公共部分,也不会接触坐标轴。沫沫控制一个位于(0,0)的弓箭手,可以朝0至90?中的任意角度(不包括0度和90度),以任意大小的力量射出带有穿透能力的光之箭。由于游戏中没有空气阻力,并且光之箭没有箭身,箭的轨迹会是一条标准的抛物线,被轨迹穿过的所有靶子都认为被沫沫射中了,包括那些...

    52014年12月4日3,149二分法,半平面交
  • 【bzoj2300】[HAOI2011]防线修建

    【bzoj2300】[HAOI2011]防线修建

    Description近来A国和B国的矛盾激化,为了预防不测,A国准备修建一条长长的防线,当然修建防线的话,肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决,到底该把哪些城市作为保护对象呢?又由于A国的经费有限,所以希望你能帮忙完成如下的一个任务:给出你所有的A国城市坐标A国上层经过讨论,考虑到经济问题,决定取消对i城市的保护,也就是说i城市不需要在防线内了A国上层询问对于剩下要保护的城市,修...

    42014年12月1日2,291凸包,离线处理
  • 【bzoj1043】[HAOI2008]下落的圆盘

    【bzoj1043】[HAOI2008]下落的圆盘

    Description有n个圆盘从天而降,后面落下的可以盖住前面的。求最后形成的封闭区域的周长。看下面这副图,所有的红色线条的总长度即为所求.Inputnrixiy1...rnxnynOutput最后的周长,保留三位小数SampleInput2100110SampleOutput10.472HINT数据规模n<=1000题解 每个圆被其它每个圆盖住的部分是一段圆弧求出这段圆弧这图是不是很丑TAT。。。根据r1^2-x^2=r2^2-(d-x)^2得x=(r2^2-r1^2+d^2)/(2*d)通过x和反三角函数就能...

    52014年11月30日2,870贪心,几何
  • 【bzoj1914】[Usaco2010 OPen]Triangle Counting 数三角形

    【bzoj1914】[Usaco2010 OPen]Triangle Counting 数三角形

    Description在一只大灰狼偷偷潜入FarmerDon的牛群被群牛发现后,贝西现在不得不履行着她站岗的职责。从她的守卫塔向下瞭望简直就是一件烦透了的事情。她决定做一些开发智力的小练习,防止她睡着了。想象牧场是一个X,Y平面的网格。她将N只奶牛标记为1…N(1<=N<=100,000),每只奶牛的坐标为X_i,Y_i(-100,000<=X_i<=100,000;-100,000<=Y_i<=100,000;1<=i<=N)。然后她脑海里想象着所有可能由奶牛...

    22014年10月29日2,067几何
  • 【想法题系列】逗比三角形

    【想法题系列】逗比三角形

    【题目描述】小J是一名OI退役滚粗文化课选手,他十分喜欢做题,尤其是裸题。他现在有一个二维盒子和一些二维三角形,这个盒子拥有无限的高度和L的宽度。而且他的三角形也都是一些锐角三角形或者是直角三角形。现在小J想把这些三角形放入盒子里,由于小J从txt大神犇那里学会了魔♂法,所以小J的三角形既可以无视盒子边界又可以重叠放置,但是必须有一条边紧贴盒子底面所在的直线。现在小J想要最大化在盒子中的被三角形覆盖的...

    02014年10月29日1,224二分法,几何
  • 【bzoj2618】[Cqoi2006]凸多边形

    【bzoj2618】[Cqoi2006]凸多边形

    Description逆时针给出n个凸多边形的顶点坐标,求它们交的面积。例如n=2时,两个凸多边形如下图:则相交部分的面积为5.233。Input第一行有一个整数n,表示凸多边形的个数,以下依次描述各个多边形。第i个多边形的第一行包含一个整数mi,表示多边形的边数,以下mi行每行两个整数,逆时针给出各个顶点的坐标。 Output输出文件仅包含一个实数,表示相交部分的面积,保留三位小数。 SampleInput26-20-1-21-22012-1240-3...

    12014年10月16日2,378半平面交