计算几何

20190211update：工作的时候看同事ocr的代码，发现有一段就是极角排序orz…所以说算法还是有用的… 先介绍几种极角排序： 1.利用叉积的正负来作cmp.(即是按逆时针排序).此题就是用这种方法

A - You can Solve a Geometry Problem too **Time Limit:**1000MS **Memory Limit:**32768KB 64bit IO Format:%I64d & %I64u Submit Status Description Many geometry（几何）problems were designed in the ACM/ICPC. And now, I also prepare a geometry problem for this final exam. According to the experience of many ACMers, geometry problems are always much trouble, but this problem is very easy, after all we are now attending an exam, not a contest :) Give you N (1<=N<=100) segments（线段）, please output the number of all intersections（交点）. You should count repeatedly if M (M>2) segments intersect at the same point.

改革春风吹满地 # **Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 24179 Accepted Submission(s): 12504 ** Problem Description " 改革春风吹满地， 不会AC没关系； 实在不行回老家， 还有一亩三分地。 谢谢！（乐队奏乐）"

B. Anton and Lines time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output The teacher gave Anton a large geometry homework, but he didn’t do it (as usual) as he participated in a regular round on Codeforces. In the task he was given a set of n lines defined by the equations y = k__i*x + b__i. It was necessary to determine whether there is at least one point of intersection of two of these lines, that lays strictly inside the strip between _x_1 < _x_2. In other words, is it true that there are1 ≤ i < j ≤ n and x’, y’, such that:

题意：给定一个六边形的六条边的长，问能分割成多少个单位正三角形． 分割不好办，那我们就反着来，先补成一个包含这个六边形的正三角形． 对于边长为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. 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 a ball and a cuboid, you need to detect whether they collide. We say that two objects collide if and only if they share at least one point.

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83295#problem/I 最多18个点，选3个点，能够成的三角形不超过1000个，O(n2)暴力就可以。 思路就是枚举三个点点，对于每一个构成的三角形，把这个三角形的最小角和次小角存起来。 然后枚举三角形，判断是否有两个三角形的最小角和次小角分别对应相等。

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

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