计算几何-111qqz的小窝

uvalive 7675 | 2016 北京 regional onsite H - A New Ground Heating Device （二分+多个圆面积并）

题目链接题意：在一个二维平面上，有n个加热设备，每个加热设备加热一个圆形，加热设备需要信号源才可以工作，信号源在原点上，但是高度不确定。假设

Posted by 111qqz Thursday, October 12, 2017

SPOJ CIRUT - CIRU2 (多个圆交，求交任意次的面积，模板题)

题目链接题意&思路：给出n个圆求恰好k个圆相交的面积，k属于1..n 先放个别人的代码。。。我真是体会到了。。。软件工程这门课的重要性

Posted by 111qqz Thursday, October 12, 2017

spoj CIRU - The area of the union of circles (多个圆面积并，模板题)

题目链接题意：多n个圆的面积并。思路：发现和求2个圆的完全不一样，具体请参考 SPOJ 8073 The area of the union of circles（计算几何の圆并）（CIRU）圆的

Posted by 111qqz Wednesday, October 11, 2017

hdu 1724 Ellipse (辛普森积分模板题)

hdu1724题目链接题意：求图示区域的面积。思路：辛普森积分学习笔记容易推出被积函数为 f(x)=b_sqrt(1-(x_x/a/a)); /* *********************************************** Author :111qqz Created Time :2017年10月09日星期一 21时0

Posted by 111qqz Monday, October 9, 2017

辛普森积分学习笔记

16沈阳的阴影还在orz，来学习一下辛普森积分。参考资料：梯形多步法和辛普森积分辛普森计算定积分辛普森积分是一种数值积分方法（然后现在只记得

Posted by 111qqz Monday, October 9, 2017

BZOJ 3680: 吊打XXX (广义费马点，模拟退火+爬山)

3680: 吊打XXX Time Limit: 10 Sec Memory Limit: 128 MBSec Special Judge Submit: 2043 Solved: 732 [Submit][Status][Discuss] Description gty又虐了一场比赛，被虐的蒟蒻们决定吊打gty。gty见大势不好机智的分出了n个分身，但还是被

Posted by 111qqz Wednesday, August 31, 2016

hdu 5017 Ellipsoid (模拟退火，计算椭球到定点的最小距离)

hdu 5017 题目链接题意：给出椭球方程的6的参数 a,b,c,d,e,f 问椭球上的点到原点(0,0,,0)的最小距离是多少。思路：感觉难点在于，如何保证搜到的点一直在椭球

Posted by 111qqz Wednesday, August 31, 2016

poj 1385 Lifting the Stone (多边形的重心)

poj 1385 题目链接题意：求多边形的重心。思路：抄模板（逃嘛。。三角形的重心是三个点坐标的平均数。。。多边形的重心其实就是先求三角形的重心然后再加权

Posted by 111qqz Monday, August 29, 2016

poj 1380 Equipment Box （简单几何）

题目链接题意：问一个小矩形能否放在一个大矩形中，给定两个矩形的尺寸。思路：主要是斜着放比较难判断。学弟貌似写了离散化角度旋转。。。我的做法是

Posted by 111qqz Sunday, August 28, 2016

BZOJ 1656: [Usaco2006 Jan] The Grove 树木(神奇的bfs之射线法)

1656: [Usaco2006 Jan] The Grove 树木 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 143 Solved: 88 [Submit][Status][Discuss] Description The pasture contains a small, contiguous grove of trees that has no ‘holes’ in the middle of the it. Bessie wonders: how far is it to walk around that grove and get back to my starting position? She’s just sure there is a way to do it by going

Posted by 111qqz Friday, April 15, 2016

codeforces #346 div 2 D. Bicycle Race (思维，计算几何，公式)

题目链接题意：给出n+1个点，每次由i点到i+1点，每段线段之间保证不同向或者反向，第一个点和最后一个点保证重合。路径围城的封闭图形中间都是

Posted by 111qqz Thursday, March 31, 2016

bzoj 1610 [Usaco2008 Feb]Line连线游戏 (计算几何)

http://www.lydsy.com/JudgeOnline/problem.php?id=1610 题意：给出n个点，问有多少条直线，这些之间之间都不平行。思路：求斜率（注意考虑斜率不存在），看有多少种斜率。妈蛋。。。。斜率不存在是横坐标

Posted by 111qqz Saturday, February 27, 2016

codeforces #339 div 2 C. Peter and Snow Blower

http://codeforces.com/contest/614/problem/C 题意：给一个多边形和多边形外一定点，多边形绕定点旋转，问多边形扫过的面积。思路：简单计算几何，找到多边形距离定点的最大和最小距离R和r,答

Posted by 111qqz Wednesday, February 17, 2016

codeforces 14 C. Four Segments

http://codeforces.com/problemset/problem/14/C 题意：给出四条边的坐标，问能否形成一个边与坐标轴平行的矩形。边可能退化成点。思路：首先第一步，检查有没有边退化成点以及是否有不平行的边。第

Posted by 111qqz Tuesday, December 29, 2015

hdu 1221 Rectangle and Circle

http://acm.hdu.edu.cn/showproblem.php?pid=1221 题意：问圆和矩形是否相交思路：主要特殊的包含情况，然后判断与线段相交。 /* *********************************************** Author :111qqz Created Time :2015年12月21日星期一 21时38分22秒 File Name :code/hdu/rr1221.cpp ************************************************

Posted by 111qqz Monday, December 21, 2015

codeforces 560 C. Gerald's Hexagon (思维，几何)

题意：给定一个六边形的六条边的长，问能分割成多少个单位正三角形．分割不好办，那我们就反着来，先补成一个包含这个六边形的正三角形．对于边长为a

Posted by 111qqz Sunday, August 16, 2015

hdoj 2436 Collision Detection

Collision Detection **Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1207 Accepted Submission(s): 367 ** Problem Description In physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given objects. Collision detection algorithms are a basic component of 3D video games. Without them, characters could go through walls and other obstacles. Here comes an interesting problem, given

Posted by 111qqz Friday, July 31, 2015

hdu 4082 I Hou Yi's secret （计算几何）

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83295#problem/I 最多18个点，选3个点，能够成的三角形不超过1000个，O(n2)暴力就可以。思路就是枚举三个点点，对于每一个构成的三角形，把这个三角形的

Posted by 111qqz Wednesday, July 22, 2015

poj 2398 Toy Storage (计算几何,判断点和线段关系)

http://poj.org/problem?id=2398 题意大概是说将一个盒子用n个board分成n+1 部分然后往里面放toy,给定盒子,board,和toy的坐标问所有的toy放完后,有多少部

Posted by 111qqz Tuesday, July 21, 2015

hdu 5120 - Intersection

题意：求两个相等的圆环的相交的面积…. 简单计算几何+容斥原理？扇形面积公式记错调了半天2333333333 这题不难&helli

Posted by 111qqz Thursday, February 19, 2015

111qqz的小窝