分类 - 计算几何

? 计算几何 ? ? 旋转卡壳 ? ? 凸包 ? ? 解题记录 ?    2018-12-10 09:00:04    447    0    0
Description Thousands of thousands years ago there was a small kingdom located in the middle of the Pacific Ocean. The territory of the kingdom consists two separated islands. Due to the impact of the ocean current, the shapes of both the islands became convex polygons. The king of the kingdom wante
? 解题记录 ? ? 洛谷 ? ? 半平面交 ?    2018-11-25 16:57:21    706    0    0
题目描述沫沫最近在玩一个二维的射箭游戏,如下图 1 所示,这个游戏中的 x 轴在地面,第一象限中有一些竖直线段作为靶子,任意两个靶子都没有公共部分,也不会接触坐标轴。 沫沫控制一个位于(0,0)的弓箭手,可以朝 0 至 90?中的任意角度(不包括 0度和 90度),以任意大小的力量射出带有穿透能力的光之箭。由于游戏中没有空气阻力,并且光之箭没有箭身,箭的轨迹会是一条标准的抛物线,被轨迹穿过的所有靶子都认为被沫沫射中了,包括那些 只有端点被射中的靶子。 这个游戏有多种模式,其中沫沫最喜欢的是闯关模式。 在闯关模式中,第一关只有一个靶 子,射中这个靶子即可进入第二关,这时在第一关的基础上会出现另外
? 解题记录 ? ? 洛谷 ? ? 半平面交 ?    2018-11-25 16:53:54    728    0    0
题目描述这里有一辆赛车比赛正在进行,赛场上一共有N辆车,分别称为个g1,g2......gn。赛道是一条无限长的直线。最初,gi位于距离起跑线前进ki的位置。比赛开始后,车辆gi将会以vi单位每秒的恒定速度行驶。在这个比赛过程中,如果一辆赛车曾经处于领跑位置的话(即没有其他的赛车跑在他的前面),这辆赛车最后就可以得奖,而且比赛过程中不用担心相撞的问题。现在给出所有赛车的起始位置和速度,你的任务就是算出那些赛车将会得奖。 输入输出格式输入格式:   第一行有一个正整数N表示赛车的个数。接下来一行给出N个整数,按顺序给出N辆赛车的起始位置。再接下来一行给出N个整数,按顺序给出N辆赛车的恒
? 解题记录 ? ? 洛谷 ? ? 二分答案 ?    2018-10-21 15:00:09    450    0    0
题目描述某人在山上种了N棵小树苗。冬天来了,温度急速下降,小树苗脆弱得不堪一击,于是树主人想用一些塑料薄膜把这些小树遮盖起来,经过一番长久的思考,他决定 用3个L*L的正方形塑料薄膜将小树遮起来。我们不妨将山建立一个平面直角坐标系,设第i棵小树的坐标为(Xi,Yi),3个L*L的正方形的边要求平行 与坐标轴,一个点如果在正方形的边界上,也算作被覆盖。当然,我们希望塑料薄膜面积越小越好,即求L最小值。 输入输出格式输入格式:   第一行有一个正整数N,表示有多少棵树。 接下来有N行,第i+1行有2个整数Xi,Yi,表示第i棵树的坐标,保证不会有2个树的坐标相同。   输出格式
? 解题记录 ? ? LOJ ? ? KD tree ?    2018-10-03 10:23:58    794    0    0
地址:https://loj.ac/problem/2586  说一说我和这道题的故事吧。打完T1的5分后我又来看到了T2。一看完了又不会,赶快打了个7分暴力。再想想,我貌似可以拿Subtask2的12分,准备打完T1来码。然后T1的400个set死活打不出来……于是乎这道题是彻底凉了。一下来就听见很多人码了个KD-tree爆艹T2,什么鬼????不过正解貌似是个线段树维护扫描线,没人写……  然后为了练习KDtree,今天又搬出这道题来。思路大概是一个节点维护能框住下面所有圆的最小矩形。嗯……就是把圆并近似成矩形判相交剪枝然后骗分。这个做法在考场上就能得到87分,都怪当年
? 解题记录 ? ? BZOJ ? ? 乱搞 ? ? 辛普森积分 ?    2018-08-13 11:17:24    1213    0    0
【题目描述】给出N个圆,求其面积并 【输入】先给一个数字N ,N< = 1000 接下来是N行是圆的圆心,半径,其绝对值均为小于1000的整数 【输出】面积并,保留三位小数 辛普森积分实在太强了……它相当于用很多1、2、3次函数去拟合一个函数以达到轻松计算积分的目的。这里给一篇博客,讲的很好:一篇博客然后有一些小小的优化:为了解决函数不连续的问题,可以设置一个限定长度,让辛普森积分只在值域范围在限定长度以内的情况下才停止递归。然后有一个精度优化,辛普森的eps可以设置成每向下递归一层就除以2,效果拔群。#include<cstdio> #include<algorith
? 解题记录 ? ? 洛谷 ? ? 平衡树 ? ? 凸包 ?    2018-04-27 21:51:34    461    0    0
题目描述近来A国和B国的矛盾激化,为了预防不测,A国准备修建一条长长的防线,当然修建防线的话,肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决,到底该把哪些城市作为保护对象呢?又由于A国的经费有限,所以希望你能帮忙完成如下的一个任务: 给出你所有的A国城市坐标 A国上层经过讨论,考虑到经济问题,决定取消对i城市的保护,也就是说i城市不需要在防线内了 A国上层询问对于剩下要保护的城市,修建防线的总经费最少是多少 你需要对每次询问作出回答。注意单位1长度的防线花费为1。 A国的地形是这样的,形如下图,x轴是一条河流,相当于一条天然防线,不需要你再修建 A国总是有两个城市在河边,一个
? 解题记录 ? ? 凸包 ? ? 洛谷 ?    2018-02-28 10:24:19    306    0    0
题目描述农夫约翰想要建造一个围栏用来围住他的奶牛,可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标,计算最短的能够围住这些点的围栏的长度。 输入输出格式输入格式:   输入数据的第一行包括一个整数 N。N(0 <= N <= 10,000)表示农夫约翰想要围住的放牧点的数目。接下来 N 行,每行由两个实数组成,Xi 和 Yi,对应平面上的放牧点坐标(-1,000,000 <= Xi,Yi <= 1,000,000)。数字用小数表示。   输出格式:   输出必须包括一个实数,表示必须的围栏的长度。答案
? 解题记录 ? ? 洛谷 ? ? 半平面交 ?    2018-02-28 10:16:12    688    0    0
题目描述逆时针给出n个凸多边形的顶点坐标,求它们交的面积。例如n=2时,两个凸多边形如下图:  则相交部分的面积为5.233。 输入输出格式输入格式:   第一行有一个整数n,表示凸多边形的个数,以下依次描述各个多边形。第i个多边形的第一行包含一个整数mi,表示多边形的边数,以下mi行每行两个整数,逆时针给出各个顶点的坐标。   输出格式:   输出文件仅包含一个实数,表示相交部分的面积,保留三位小数。   输入输出样例输入样例#1: 复制2 6 -2 0 -1 -2 1 -2 2 0 1&nb
? 解题记录 ? ? 洛谷 ? ? 旋转卡壳 ? ? 凸包 ?    2018-02-28 10:10:02    628    0    0
题目描述给定一些点的坐标,要求求能够覆盖所有点的最小面积的矩形,输出所求矩形的面积和四个顶点坐标 输入输出格式输入格式:   第一行为一个整数n(3<=n<=50000),从第2至第n+1行每行有两个浮点数,表示一个顶点的x和y坐标,不用科学计数法   输出格式:   第一行为一个浮点数,表示所求矩形的面积(精确到小数点后5位),接下来4行每行表示一个顶点坐标,要求第一行为y坐标最小的顶点,其后按逆时针输出顶点坐标.如果用相同y坐标,先输出最小x坐标的顶点   输入输出样例输入样例#1: 复制6 1.0 3.00