• 离大海最远点在哪里?

    离大海最远点在哪里?

    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,627STL,链表,二分法,半平面交
  • 【bzoj3190】[JLOI2013]赛车

    【bzoj3190】[JLOI2013]赛车

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

    42014年12月25日2,071半平面交
  • 【bzoj2732】[HNOI2012]射箭

    【bzoj2732】[HNOI2012]射箭

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

    52014年12月4日2,594二分法,半平面交
  • 【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日1,983半平面交
  • 【bzoj1038】[ZJOI2008]瞭望塔

    【bzoj1038】[ZJOI2008]瞭望塔

    Description致力于建设全国示范和谐小村庄的H村村长dadzhi,决定在村中建立一个瞭望塔,以此加强村中的治安。我们将H村抽象为一维的轮廓。如下图所示我们可以用一条山的上方轮廓折线(x1,y1),(x2,y2),….(xn,yn)来描述H村的形状,这里x1<x2<…<xn。瞭望塔可以建造在[x1,xn]间的任意位置,但必须满足从瞭望塔的顶端可以看到H村的任意位置。可见在不同的位置建造瞭望塔,所需要建造的高度是不同的。为了节省开支,dadzhi...

    82014年10月16日2,303半平面交
  • 【poj2451】Uyuw’s Concert

    【poj2451】Uyuw's Concert

    DescriptionPrinceRemmargutssolvedtheCHESSpuzzlesuccessfully.Asanaward,UyuwplannedtoholdaconcertinahugepiazzanamedafteritsgreatdesignerIhsnayish.ThepiazzainUDF-UnitedDeltaofFreedom’sdowntownwasasquareof[0,10000]*[0,10000].Somebasketchairshadbeenstandingthereforyears,butinaterriblemess.Lookatthefollowinggraph.Inthiscasewehavethreechairs,andtheaudiencesfacethedirectionaswhatarro...

    132014年10月4日1,740半平面交