题目链接 题意：给出n+1个点，每次由i点到i+1点，每段线段之间保证不同向或者反向，第一个点和最后一个点保证重合。路径围城的封闭图形中间都是水，问有多少个危险点，使得如果在这个点忘记转弯就会掉进水里。 思路：搞了半天没搞出来qaq From the track description follows that Maria moves the way that the water always located to the right from her, so she could fall into the water only while turning left. To check if the turn is to the …

http://www.lydsy.com/JudgeOnline/problem.php?id=1610 题意：给出n个点，问有多少条直线，这些之间之间都不平行。 思路：求斜率（注意考虑斜率不存在），看有多少种斜率。 妈蛋。。。。斜率不存在是横坐标相等啊，不是纵坐标啊。。。蠢哭了好么。。。。。。 妈蛋。。。。斜率不存在是横坐标相等啊，不是纵坐标啊。。。蠢哭了好么。。。。。。 妈蛋。。。。斜率不存在是横坐标相等啊，不是纵坐标啊。。。蠢哭了好么。。。。。。 太他妈惨了。。。。 /* *********************************************** Author :111qqz Created Time …

http://codeforces.com/contest/614/problem/C 题意：给一个多边形和多边形外一定点，多边形绕定点旋转，问多边形扫过的面积。 思路：简单计算几何，找到多边形距离定点的最大和最小距离R和r,答案就是(R^2-R^2)*PI 需要注意的是：最大距离一定是从某点上取得，但是最小距离可能不在顶点上，而在某条边上。 /* *********************************************** Author :111qqz Created Time :2016年02月16日 星期二 16时58分59秒 File Name :code/cf/problem/614C.cpp …

http://codeforces.com/problemset/problem/14/C 题意：给出四条边的坐标，问能否形成一个边与坐标轴平行的矩形。边可能退化成点。 思路：首先第一步，检查有没有边退化成点以及是否有不平行的边。 第二步，检查两个方向的边是否各有两条。。 第三步，将所有点的坐标排序。。然后看8个点是否会因为重合而变成4个.。 /* *********************************************** Author :111qqz Created Time :2015年12月29日 星期二 16时28分28秒 File Name :code/cf/problem/14C.cpp …

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 ************************************************ */ #include <iostream> #include …

题意：给定一个六边形的六条边的长，问能分割成多少个单位正三角形． 分割不好办，那我们就反着来，先补成一个包含这个六边形的正三角形． 对于边长为a的正三角形，显然我们可以分割成a*a个单位正三角形 大正三角形的边长为连续的三条边的和 而要减掉的三个小三角形的边长为与之前连续的三条边的起始边的序号的奇偶性相同的三条边． 就是说如果求和的时候求的是前三条边，那么三个要减掉的小三角形的边长就是第一，三，五条边． 如果求和的时候求的是后三条边，那么三个要减掉的小三角形的边长就是第二，第四，第六条边． …

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. …

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83295#problem/I 最多18个点，选3个点，能够成的三角形不超过1000个，O(n2)暴力就可以。 思路就是枚举三个点点，对于每一个构成的三角形，把这个三角形的最小角和次小角存起来。 然后枚举三角形，判断是否有两个三角形的最小角和次小角分别对应相等。 需要注意的是题目中问的是相似三角形的最大个数 如果A B 相似 C D 相似，但是B C 不相似，答案应该是2. 还有三角形自身和自身是相似的。 一开始求角度的时候只求了cos值，忘了求下acos了。 需要注意的是，枚举的到时候，三个点可能共线，这个还挺好，题目中说的 …

http://poj.org/problem?id=2398 题意大概是说将一个盒子用n个board分成n+1 部分 然后往里面放toy,给定盒子,board,和toy的坐标 问所有的toy放完后,有多少部分中有t个toy; 简单计算几何 需要判断的是点和直线的关系. 判断 某一点在直线左右侧 左右方向是相对前进方向的,只要指定了前进方向就可以知道左右(比如指定前进方向是从直线的起点到终点).判断点在直线的左侧还是右侧是计算几何里面的一个最基本算法.使用矢量来判断. 定义：平面上的三点P1(x1,y1),P2(x2,y2),P3(x3,y3)的面积量： ** S(P1,P2,P3)=|y1 y2 y3|= …

题意：求两个相等的圆环的相交的面积.... 简单计算几何+容斥原理？ 扇形面积公式记错调了半天2333333333 这题不难...倒是从学长那里收获了几点关于代码规范的问题... 听说了学长在北京区域赛时把PI定义错了一位结果一直WA的教训.... 以后还是写acos(-1)吧 局部变量和全局变量因为【想怎么其变量名想得整个人都不好了】就起成了一样的...被学长给了差评。 哦，对！还有一个就是发现了cmath库里有一个奇葩的函数名叫y1.。。。。。。。 —————————————————————————————————————————————— 竟然CE了 提示 error:pow(int,int) is ambiguous 看来我 …