acm-计算几何模板

Computational Geometry
计算几何教程
计算几何的恶心之处
代码长，难写。
需要讨论各种边界情况。后面所介绍的算
法，有些对于边界情况的处理很完美，不 需要再做讨论；有些则不然，需要自行处 理边界情况。
精度误差

二维矢量
2-Dimension Vector
矢量
既有大小又有方向的量。
算法演示
2 被弹出栈，3 进栈。
算法演示
没有点被弹出栈，4 进栈。
算法演示
4 被弹出栈，5 进栈。
算法演示
5 被弹出栈，6 进栈。
算法演示
6 被弹出栈，7 进栈。
算法演示
如此直到下凸壳被找到。
算法演示
倒序进行扫描找到上凸壳。
Graham 扫描的时间复杂度
这太傻缺了。算法的瓶颈在排序，所以时
总时间复杂度 O(N2 log N)。
算法扩展
SPOJ CIRUT
求恰好被覆盖 1 次、2 次、„、N 次的面积。
算法的本质在于对“裸露”部分进行处理。
这种方法也可以用于求很多圆与很多凸多 边形的面积并——但是情况复杂得多，要 讨论的情况也多得多。
三维矢量
3-Dimension Vector
总体来说讨论比较辛苦，写起来不算很难。
精度存在比较大的问题，而且半平面交的
题目一般都容许 O(N2) 算法，所以并不是 很常用。
半平面交练习题
POJ 1279 POJ 3525 POJ 2451 POJ 3384
求多边形的核。核中的点满足其到多边形边 界上任一点之间的线段只与多边形在那一点相交。 求凸多边形最大内切圆半径。 裸的半平面交。朱泽园专门为他的算法出的 题，要求 O(N log N) 算法。 求在凸多边形内部放两个半径为 r 的圆所能 覆盖的最大面积。两圆可以重叠，但不能与多边形相交。 需要用到旋转卡壳。

1.扇形的重心Xc = 2*R*sinA/3/A （A为圆心角的一半）2.N点中三个点组成三角形面积最大#include <stdio.h>#include <stdlib.h>#include <math.h>#define MaxNode 50005int stack[MaxNode];int top;double max;typedef struct TPoint{int x;int y;}TPoint;TPoint point[MaxNode];void swap(TPoint point[], int i, int j){TPoint tmp;tmp = point[i];point[i] = point[j];point[j] = tmp;}double multi(TPoint p1, TPoint p2, TPoint p0){return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y); }double distance(TPoint p1, TPoint p2){return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);}int cmp(const void *a, const void *b){TPoint *c = (TPoint *)a;TPoint *d = (TPoint *)b;double k = multi(*c, *d, point[0]);if(k< 0) return 1;else if(k == 0 && distance(*c, point[0]) >= distance(*d, point[0])) return 1;else return -1;}void grahamScan(int n){//Graham扫描求凸包int i, u;//将最左下的点调整到p[0]的位置u = 0;for(i = 1;i <= n - 1;i++){if((point[i].y < point[u].y) ||(point[i].y == point[u].y && point[i].x < point[u].x)) u = i;}swap(point, 0, u);//将平p[1]到p[n - 1]按按极角排序，可采用快速排序qsort(point + 1, n - 1, sizeof(point[0]), cmp);for(i = 0;i <= 2;i++) stack[i] = i;top = 2;for(i = 3;i <= n - 1;i++){while(multi(point[i], point[stack[top]], point[stack[top - 1]]) >= 0){ top--;if(top == 0) break;}top++;stack[top] = i;}}int main(){double triangleArea(int i, int j, int k);void PloygonTriangle();int i, n;while(scanf("%d", &n) && n != -1){for(i = 0;i < n;i++)scanf("%d%d", &point[i].x, &point[i].y);if(n <= 2){printf("0.00\n");continue;}if(n == 3){printf("%.2lf\n", triangleArea(0, 1, 2));continue;}grahamScan(n);PloygonTriangle();printf("%.2lf\n", max);}return 0;}void PloygonTriangle(){double triangleArea(int i, int j, int k);int i, j , k;double area, area1;max = -1;for(i = 0;i <= top - 2;i++){k = -1;for(j = i + 1; j <= top - 1;j++){if(k <= j) k= j + 1;area = triangleArea(stack[i], stack[j], stack[k]);if(area > max) max = area;while(k + 1 <= top){area1= triangleArea(stack[i], stack[j], stack[k + 1]);if(area1 < area) break;if(area1 > max) max = area1;area = area1;k++;}}}}double triangleArea(int i, int j, int k){//已知三角形三个顶点的坐标，求三角形的面积double l = fabs(point[i].x * point[j].y + point[j].x * point[k].y + point[k].x * point[i].y - point[j].x * point[i].y- point[k].x * point[j].y - point[i].x * point[k].y) / 2;return l;}3.N个点最多组成多少个正方形#include<stdio.h>#include<stdlib.h>#include<math.h>#define eps 1e-6#define pi acos(-1.0)#define PRIME 9991struct point{int x, y;}p[2201];int n;struct HASH{int cnt;int next;}hash[50000];int hashl;int Hash(int n){int i = n % PRIME;while(hash[i].next != -1){if(hash[hash[i].next].cnt == n) return 1;else if(hash[hash[i].next].cnt > n) break;i = hash[i].next;}hash[hashl].cnt = n;hash[hashl].next = hash[i].next;hash[i].next = hashl;hashl++;return 0;}int Hash2(int n){int i = n % PRIME;while(hash[i].next != -1){if(hash[hash[i].next].cnt == n) return 1;else if(hash[hash[i].next].cnt > n) return 0;i = hash[i].next;}return 0;}int check(double ax, double ay, int &x, int &y){int a0 = (int)ax;int b0 = (int)ay;int tag1 = 0, tag2 = 0;if(fabs(a0 - ax) < eps){tag1 = 1;x = a0;}else if(fabs(a0 + 1 - ax) < eps){tag1 = 1;x = a0 + 1;}if(fabs(b0 - ay) < eps){tag2 = 1;y = b0;}else if(fabs(b0 + 1 - ay) < eps){y = b0 + 1;tag2 = 1;}if(tag1 == 1 && tag2 == 1) return 1;else return 0;}int squares(point p1, point p2, point &p3, point &p4) {double a = (double)p2.x - p1.x;double b = (double)p2.y - p1.y;double midx = ((double)p1.x + p2.x) / 2;double midy = ((double)p1.y + p2.y) / 2;double tmp = a * a + b * b;double x1 = sqrt(b * b) / 2;double y1;if(fabs(b) < eps) y1 = sqrt(a * a + b * b) / 2;else y1 = -a * x1 / b;x1 += midx;y1 += midy;if(check(x1, y1, p3.x, p3.y) == 0) return 0;x1 = 2 * midx - x1;y1 = 2 * midy - y1;if(check(x1, y1, p4.x, p4.y) == 0) return 0;return 1;}int main(){int i, j, cnt;while(scanf("%d", &n) != EOF && n){for(i = 0;i < PRIME;i++) hash[i].next = -1;hashl = PRIME;int x1, y1, x2, y2;for (i = 0; i < n; i++){scanf("%d%d", &p[i].x, &p[i].y);Hash((p[i].x + 100000) * 100000 + p[i].y + 100000);}cnt = 0;for (i = 0; i < n; i++){for (j = i + 1; j < n; j++){point a, b;if(squares(p[i], p[j], a, b) == 0) continue;if(Hash2((a.x + 100000) * 100000 + a.y + 100000) == 0) continue;if(Hash2((b.x + 100000) * 100000 + b.y + 100000) == 0) continue;cnt++;}}printf("%d\n", cnt / 2);}return 0;}4.单位圆覆盖最多点/*平面上N个点，用一个半径R的圆去覆盖，最多能覆盖多少个点？比较经典的题目。

/*计算几何目录㈠点的基本运算1. 平面上两点之间距离12. 判断两点是否重合13. 矢量叉乘14. 矢量点乘25. 判断点是否在线段上26. 求一点饶某点旋转后的坐标27. 求矢量夹角2㈡线段及直线的基本运算1. 点与线段的关系32. 求点到线段所在直线垂线的垂足43. 点到线段的最近点44. 点到线段所在直线的距离45. 点到折线集的最近距离46. 判断圆是否在多边形内57. 求矢量夹角余弦58. 求线段之间的夹角59. 判断线段是否相交610.判断线段是否相交但不交在端点处611.求线段所在直线的方程612.求直线的斜率713.求直线的倾斜角714.求点关于某直线的对称点715.判断两条直线是否相交及求直线交点716.判断线段是否相交，如果相交返回交点7㈢多边形常用算法模块1. 判断多边形是否简单多边形82. 检查多边形顶点的凸凹性93. 判断多边形是否凸多边形94. 求多边形面积95. 判断多边形顶点的排列方向，方法一106. 判断多边形顶点的排列方向，方法二107. 射线法判断点是否在多边形内108. 判断点是否在凸多边形内119. 寻找点集的graham算法1210.寻找点集凸包的卷包裹法1311.判断线段是否在多边形内1412.求简单多边形的重心1513.求凸多边形的重心1714.求肯定在给定多边形内的一个点1715.求从多边形外一点出发到该多边形的切线1816.判断多边形的核是否存在19㈣圆的基本运算1 .点是否在圆内202 .求不共线的三点所确定的圆21㈤矩形的基本运算1.已知矩形三点坐标，求第4点坐标22㈥常用算法的描述22㈦补充1．两圆关系：242．判断圆是否在矩形内：243．点到平面的距离：254．点是否在直线同侧：255．镜面反射线：256．矩形包含：267．两圆交点：278．两圆公共面积：289. 圆和直线关系：2910. 内切圆：3011. 求切点：3112. 线段的左右旋：3113．公式：32*//* 需要包含的头文件*/#include <cmath >/* 常用的常量定义*/const double INF = 1E200const double EP = 1E-10const int MAXV = 300const double PI = 3.14159265/* 基本几何结构*/struct POINT{double x;double y;POINT(double a=0, double b=0) { x=a; y=b;} //constructor};struct LINESEG{POINT s;POINT e;LINESEG(POINT a, POINT b) { s=a; e=b;}LINESEG() { }};struct LINE // 直线的解析方程a*x+b*y+c=0 为统一表示，约定a >= 0{double a;double b;double c;LINE(double d1=1, double d2=-1, double d3=0) {a=d1; b=d2; c=d3;}};/*********************** ** 点的基本运算** ***********************/double dist(POINT p1,POINT p2) // 返回两点之间欧氏距离{return( sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ) );}bool equal_point(POINT p1,POINT p2) // 判断两个点是否重合{return ( (abs(p1.x-p2.x)<EP)&&(abs(p1.y-p2.y)<EP) );}/****************************************************************************** r=multiply(sp,ep,op),得到(sp-op)和(ep-op)的叉积r>0：ep在矢量opsp的逆时针方向；r=0：opspep三点共线；r<0：ep在矢量opsp的顺时针方向******************************************************************************* /double multiply(POINT sp,POINT ep,POINT op){return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y));}/*r=dotmultiply(p1,p2,op),得到矢量(p1-op)和(p2-op)的点积，如果两个矢量都非零矢量r<0：两矢量夹角为锐角；r=0：两矢量夹角为直角；r>0：两矢量夹角为钝角******************************************************************************* /double dotmultiply(POINT p1,POINT p2,POINT p0){return ((p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y));}/****************************************************************************** 判断点p是否在线段l上条件：(p在线段l所在的直线上) && (点p在以线段l为对角线的矩形内)******************************************************************************* /bool online(LINESEG l,POINT p){return( (multiply(l.e,p,l.s)==0) &&( ( (p.x-l.s.x)*(p.x-l.e.x)<=0 )&&( (p.y-l.s.y)*(p.y-l.e.y)<=0 ) ) ); }// 返回点p以点o为圆心逆时针旋转alpha(单位：弧度)后所在的位置POINT rotate(POINT o,double alpha,POINT p){POINT tp;p.x-=o.x;p.y-=o.y;tp.x=p.x*cos(alpha)-p.y*sin(alpha)+o.x;tp.y=p.y*cos(alpha)+p.x*sin(alpha)+o.y;return tp;}/* 返回顶角在o点，起始边为os，终止边为oe的夹角(单位：弧度)角度小于pi，返回正值角度大于pi，返回负值可以用于求线段之间的夹角原理：r = dotmultiply(s,e,o) / (dist(o,s)*dist(o,e))r'= multiply(s,e,o)r >= 1 angle = 0;r <= -1 angle = -PI-1<r<1 && r'>0 angle = arccos(r)-1<r<1 && r'<=0 angle = -arccos(r)*/double angle(POINT o,POINT s,POINT e){double cosfi,fi,norm;double dsx = s.x - o.x;double dsy = s.y - o.y;double dex = e.x - o.x;double dey = e.y - o.y;cosfi=dsx*dex+dsy*dey;norm=(dsx*dsx+dsy*dsy)*(dex*dex+dey*dey);cosfi /= sqrt( norm );if (cosfi >= 1.0 ) return 0;if (cosfi <= -1.0 ) return -3.1415926;fi=acos(cosfi);if (dsx*dey-dsy*dex>0) return fi; // 说明矢量os 在矢量oe的顺时针方向return -fi;}/*****************************\* ** 线段及直线的基本运算** *\*****************************//* 判断点与线段的关系,用途很广泛本函数是根据下面的公式写的，P是点C到线段AB所在直线的垂足AC dot ABr = ---------||AB||^2(Cx-Ax)(Bx-Ax) + (Cy-Ay)(By-Ay)= -------------------------------L^2r has the following meaning:r=0 P = Ar=1 P = Br<0 P is on the backward extension of ABr>1 P is on the forward extension of AB0<r<1 P is interior to AB*/double relation(POINT p,LINESEG l){LINESEG tl;tl.s=l.s;tl.e=p;return dotmultiply(tl.e,l.e,l.s)/(dist(l.s,l.e)*dist(l.s,l.e));}// 求点C到线段AB所在直线的垂足PPOINT perpendicular(POINT p,LINESEG l){double r=relation(p,l);POINT tp;tp.x=l.s.x+r*(l.e.x-l.s.x);tp.y=l.s.y+r*(l.e.y-l.s.y);return tp;}/* 求点p到线段l的最短距离,并返回线段上距该点最近的点np注意：np是线段l上到点p最近的点，不一定是垂足*/double ptolinesegdist(POINT p,LINESEG l,POINT &np){double r=relation(p,l);if(r<0){np=l.s;return dist(p,l.s);}if(r>1){np=l.e;return dist(p,l.e);}np=perpendicular(p,l);return dist(p,np);}// 求点p到线段l所在直线的距离,请注意本函数与上个函数的区别double ptoldist(POINT p,LINESEG l){return abs(multiply(p,l.e,l.s))/dist(l.s,l.e);}/* 计算点到折线集的最近距离,并返回最近点.注意：调用的是ptolineseg()函数*/double ptopointset(int vcount,POINT pointset[],POINT p,POINT &q) {int i;double cd=double(INF),td;LINESEG l;POINT tq,cq;for(i=0;i<vcount-1;i++)l.s=pointset[i];l.e=pointset[i+1];td=ptolinesegdist(p,l,tq);if(td<cd){cd=td;cq=tq;}}q=cq;return cd;}/* 判断圆是否在多边形内.ptolineseg()函数的应用2 */bool CircleInsidePolygon(int vcount,POINT center,double radius,POINT polygon[]){POINT q;double d;q.x=0;q.y=0;d=ptopointset(vcount,polygon,center,q);if(d<radius||fabs(d-radius)<EP)return true;elsereturn false;}/* 返回两个矢量l1和l2的夹角的余弦(-1 --- 1)注意：如果想从余弦求夹角的话，注意反余弦函数的定义域是从0到pi */double cosine(LINESEG l1,LINESEG l2){return (((l1.e.x-l1.s.x)*(l2.e.x-l2.s.x) +(l1.e.y-l1.s.y)*(l2.e.y-l2.s.y))/(dist(l1.e,l1.s)*dist(l2.e,l2.s))) );}// 返回线段l1与l2之间的夹角单位：弧度范围(-pi，pi)double lsangle(LINESEG l1,LINESEG l2){POINT o,s,e;o.x=o.y=0;s.x=l1.e.x-l1.s.x;s.y=l1.e.y-l1.s.y;e.x=l2.e.x-l2.s.x;e.y=l2.e.y-l2.s.y;return angle(o,s,e);// 如果线段u和v相交(包括相交在端点处)时，返回true////判断P1P2跨立Q1Q2的依据是：( P1 - Q1 ) ×( Q2 - Q1 ) * ( Q2 - Q1 ) ×( P2 - Q1 ) >= 0。

ACM_10[1].计算⼏何Computational GeometryComputational GeometryPrerequisitesGraph TheoryShortest PathToolsThis module discusses several algorithms that calculate various geometric properties,mostly based on only two operations described below: cross product and arctangent.Cross ProductThe cross product of u and v is written as u x v. Computationally, the cross product of twothree?dimensional vectors u and v is the vector determinant of the following matrix (where i, j, and k are unit vectors in the x, y, and z directions respectively):| i j k || ux uy uz || vx vy vz |That equation works out to:(u y v z?u z v y)i + (u z v x?u x v z)j + (u x v y?u y v x)k1Dot productThe dot product of two vectors u and v is a scalar written as u * v. Computationally, it is defined in three dimensions as: u x v x + u y v y + u z v zThe dot product is actually equal to the product of:the length of uthe length of vthe cosine of the angle between u and v.Presuming u and v are non?zero, if the dot product if negative, u and v make an angle greater than 90 degrees. If it is zero, then u and v are perpendicular. If u cdot v is positive, then the two vectors form an acute angle.ArctangentThe arctangent function calculates the (an) angle whose tangent is its argument and generally returns a real number between ?pi/2 and pi/2. An additional function in C, atan2, takes two arguments: a DELTA y value and a DELTA x value (in that order!). It determines the angle between the given vector and the positive x axis and returns a value between ?pi and pi.This has the advantage of removing concerns about dividing by zero or writing code to repair angles in order to handle the negative x cases. The atan2 function is almost always easier to use than the simpler atan function that takes only one argument.Particular Debugging ProblemsThe main problem with geometric problems is that they spawn a lot of special cases. Be on the lookout for these special cases and make sure your program works for all of them.Floating point calculations also create a new set of problems. Floating point calculations are rarely precise, as the computer only maintains so many bits (digits) of accuracy: be aware of this. In particular, when checking if two values are equal, check to see if they are within some small tolerance of each other not precisely equal.Geometric AlgorithmsHere are some of snippets that can help you solve geometry problems.Area of TriangleTo calculate the area of a triangle with vertices (a, b, c), pick a vertex (say a) and create a vector to the other two vertices (let u = b ? a, and v = c ? a). The area of the triangle (a, b, c) is one half the length of cross product u x v.Computational GeometryAn alternative method to find the area of triangle is to use Hero's formula. If the lengths of the sides of a triangle are a, b, and c, let s = (a+b+c)/2. The area of the triangle is thensqrt(s* (s?a)*(s?b)*(s?c)) .Are Two Line Segments Parallel?To check if two line segments are parallel, create vectors along each line segment and check to see if their cross product is (almost) zero.Area of polygonThe area of a polygon with vertices (x 1, y 1), ..., (x n, y n) is equal to the determinant:1 | x1 x2 ... xn || |2 | y1 y2 ... yn |where the determinate is defined to be similar to the 2 by 2 determinant: x1 y2 + x2y3 + ... +x n y1 ? y1 x2 ? y2x3 ? ... ? y n x1Distance from a point to a lineThe distance from a point P to a line AB is given by the magnitude of the cross product. In particular, d(P,AB) = |(P ? A) x (B ?A)| / | B ? A| .To determine the distance from a point P to the plane defined by A, B, and C, let n = (B ? A) x (C ? A). The distance is then give by the following equation: d(P,ABC) = (P?A) * n / |n|. Points on a lineA point is on a line if the distance from the point to the line is 0.Points on the same side of lineThis notion only makes sense for two dimensions. To check if points C and D are on the same side of line AB, calculate the z component of (B ? A) x (C ? A) and (B ? A) x (D ? A). If the z components have the same sign (i.e., their product is positive), then C and D are on the same side of the line AB.Point on line segmentTo calculate if a point C is on the line segment AB, check if C is on the line AB. If it is, then check if the length of AB is equal to the sum of the lengths of AC and CB.Point in triangleTo check if a point A is in a triangle, find another point B which is within the triangle (the average of the three vertices works well). Then, check if the point A is on the same side of the three lines defined by the edges of the triangle as B.3Computational GeometryGraph ProblemsSometimes what may look like a geometric problem is really a graph problem. Just because the input is points in the plane does not mean it's a geometric algorithm.Example ProblemsPoint MovingGiven a set of line segments in the plane, and two points A and B, is it possible to move from A to B without crossing any of the segments?The line segments partition the plane into regions. Determine these regions, and see if A and B reside in the same region. Bicycle RoutingGiven a collection of non?intersecting buildings along with start and end locations, find the shortest path from A to B that doesn't go through any buildings.Analysis: This is really a graph problem. The nodes are the start and end locations, along with the vertices of the buildings. There are edges between any two nodes such that the line segment between them does not intersect any buildings, with weight equal to the length of the length of the line segments. Once that graph has been calculated, the problem is shortest path.Maximizing Line IntersectionsGiven a collection of segments in the plane, find the greatest number of segments which can by intersected by drawing a single line.Analysis: With a little bit of thought, it is clear that the line segment must pass through twoof the vertices of the collection of line segments. Thus, try all pairs of vertices, and calculate the crossing for each. Combining this with partitioning gives an algorithm that runs fairly quickly.Polygon ClassificationGiven a collection of segments defining a polygon, determine if it is simple (no twonon?consecutive line segments intersect) and convex.7。

计算几何模板
ACM@HIT
Au分 1.几何公式.............................................................................................................................................. 5 1.1 三角形 ....................................................................................................................................... 5 1.2 四边形 ....................................................................................................................................... 5 1.3 正 n 边形 ...................................................................................................................................5 1.4 圆............................................................................................................................................... 5 1.5 棱柱.........................................

专用模板目录：一、图论1．最大团2．拓扑排序3．最短路和次短路4．SAP模板5．已知各点度，问能否组成一个简单图6．KRUSKAL7. Prim算法求最小生成树8. Dijkstra9 . Bellman-ford10. SPFA11. Kosaraju 模板12. tarjan 模板二、数学1. 剩余定理2. N!中质因子P的个数3.拓展欧几里得4.三角形的各中心到顶点的距离和5.三角形外接圆半径周长6.归并排序求逆序数7. 求N！的位数8.欧拉函数9. Miller-Rabin,大整数分解，求欧拉函数10. 第一类斯特林数11.计算表达式12.约瑟夫问题13．高斯消元法14. Baby-step,giant-step n是素数.n任意15. a^b%c=a ^(b%eular(c)+eular(c)) % c16.判断第二类斯特林数的奇偶性17.求组合数C(n,r)18.进制转换19.Ronberg算法计算积分20.行列式计算21. 返回x 的二进制表示中从低到高的第i位22.高精度运算 +-*/23.超级素数筛选三、数据结构1．树状数组2.线段树求区间的最大、小值3.线段树求区间和4.单调队列5.KMP模板6. 划分树，求区间第k小数7.最大堆，最小堆模板8. RMQ模板求区间最大、最小值9.快速排序，归并排序求逆序数.10.拓展KMP四、计算几何1.凸包面积2.Pick公式求三角形内部有多少点3.多边形边上内部各多少点以及面积pick4.平面最远点对5.判断矩形是否在矩形内6.判断点是否在多边形内7.判断4个点(三维)是否共面8.凸包周长9.等周定理变形一直两端点和周长求最大面积10.平面最近点对11.单位圆最多覆盖多少点(包括边上)12.多边形费马点求点到多边形各个点的最短距离13.矩形并周长14.zoj 2500 求两球体积并一、图论1.最大团#include<iostream>#include<algorithm>using namespace std;int n,m;int cn;//当前顶点数int best;//当前最大顶点数int vis[50];//当前解int bestn[50];//最优解int map[50][50];//临界表void dfs(int i){if(i>n){for(int j=1;j<=n;j++) bestn[j]=vis[j];best=cn;return ;}int ok=1;for(int j=1;j<i;j++){if(vis[j]==1&&map[i][j]==0){ok=0;break;}}if(ok){//进入左子树vis[i]=1;cn++;dfs(i+1);cn--;}if(cn+n-i>best){//进入右子树vis[i]=0;dfs(i+1);}}int main(){while(scanf("%d%d",&n,&m)==2){memset(vis,0,sizeof(vis));memset(map,0,sizeof(map));while(m--){int p,q;scanf("%d%d",&p,&q);map[p][q]=map[q][p]=1;//无向图}cn=0;best=0;dfs(1);printf("%d\n",best);}return 0;}2.拓扑排序#include<iostream>#include<cstring>using namespace std;int map[105][105],in[105],vis[105],ans[105],n;int flag;void dfs(int step){if(flag) return ;if(step==n+1) {flag=1; printf("%d",ans[1]);for(int i=2;i<=n;i++) printf(" %d",ans[i]);printf("\n");return ;}for(int i=1;i<=n;i++){if(vis[i]==0&&in[i]==0){vis[i]=1;for(int j=1;j<=n;j++){if(map[i][j]>0){map[i][j]=-map[i][j];in[j]--;}}ans[step]=i;dfs(step+1);vis[i]=0;for(int j=1;j<=n;j++){if(map[i][j]<0){map[i][j]=-map[i][j];in[j]++;}}}}}int main(){while(scanf("%d",&n)==1){flag=0;memset(map,0,sizeof(map));memset(vis,0,sizeof(vis));memset(in,0,sizeof(in));for(int i=1;i<=n;i++){int t;while(scanf("%d",&t),t){map[i][t]=1;in[t]++;}}dfs(1);}return 0;}3．最短路和次短路#include<iostream>#include<cstdio>#include<vector>#include<cstring>using namespace std;class Node{public:int e,w;//表示终点和边权};const int inf=(1<<25);int main(){int ci;cin>>ci;while(ci--){vector<Node> G[1005];//用邻接表存边int n,m;cin>>n>>m;for(int i=1;i<=m;i++){Node q;int u;cin>>u>>q.e>>q.w;G[u].push_back(q);}int s,f;//起点和终点cin>>s>>f;//dijkstra 求最短路和次短路int flag[1005][2];int dis[1005][2],cnt[1005][2];//0表示最短路，1表示次短路memset(flag,0,sizeof(flag));for(int i=1;i<=n;i++) dis[i][0]=dis[i][1]=inf;dis[s][0]=0;cnt[s][0]=1;//初始化for(int c=0;c<2*n;c++) //找最短路和次短路，故要进行2*n次循环也可以改成while(1){int temp=inf,u=-1,k;//找s-S'集合中的最短路径,u记录点的序号，k记录是最短路或者是次短路for(int j=1;j<=n;j++){if(flag[j][0]==0&&temp>dis[j][0]) temp=dis[j][0],u=j,k=0;else if(flag[j][1]==0&&temp>dis[j][1]) temp=dis[j][1],u=j,k=1;}if(temp==inf) break;//S'集合为空或者不联通，算法结束//更新路径flag[u][k]=1;for(int l=0;l<G[u].size();l++){int d=dis[u][k]+G[u][l].w,j=G[u][l].e;//important//4种情况if(d<dis[j][0]){dis[j][1]=dis[j][0];cnt[j][1]=cnt[j][0];dis[j][0]=d;cnt[j][0]=cnt[u][k];}else if(d==dis[j][0]){cnt[j][0]+=cnt[u][k];}else if(d<dis[j][1]){dis[j][1]=d;cnt[j][1]=cnt[u][k];}else if(d==dis[j][1]){cnt[j][1]+=cnt[u][k];}}}int num=cnt[f][0];//最短路int cc=cnt[f][1];//次短路}return 0;}4．SAP模板#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int inf=(1<<31)-1;const int point_num=300;int cap[point_num][point_num],dist[point_num],gap[point_num];//初始化见main里面int s0,t0,n;//源,汇和点数int find_path(int p,int limit=0x3f3f3f3f){if(p==t0) return limit;for(int i=0;i<n;i++)if(dist[p]==dist[i]+1 && cap[p][i]>0){int t=find_path(i,min(cap[p][i],limit));if(t<0) return t;if(t>0){cap[p][i]-=t;cap[i][p]+=t;return t;}}int label=n;for(int i=0;i<n;i++) if(cap[p][i]>0) label=min(label,dist[i]+1);if(--gap[dist[p]]==0 || dist[s0]>=n ) return -1;++gap[dist[p]=label];return 0;}int sap(){//初始化s,ts0=0,t0=n-1;int t=0,maxflow=0;gap[0]=n;while((t=find_path(s0))>=0) maxflow+=t;return maxflow;}int main(){int ci;while(cin>>ci>>n){//初始化memset(cap,0,sizeof(cap));memset(dist,0,sizeof(dist));memset(gap,0,sizeof(gap));//初始化capwhile(ci--){int x,y,c;cin>>x>>y>>c;x--;y--;cap[x][y]+=c;//因题而异}int ans=sap();cout<<ans<<endl;}return 0;}5．已知各点度，问能否组成一个简单图#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int inf=(1<<30);int d[1100];bool cmp(int x,int y){return x>y;}int main(){int ci;scanf("%d",&ci);while(ci--){int n,flag=1,cnt=0;scanf("%d",&n); for(int i=0;i<n;i++){scanf("%d",&d[i]);if(d[i]>n-1||d[i]<=0) flag=0; cnt+=d[i];}if(flag==0||cnt%2){printf("no\n");continue;}sort(d,d+n,cmp);for(int l=n;l>0;l--){for(int i=1;i<l&&d[0];i++){d[0]--,d[i]--;if(d[i]<0){flag=0;break;}}if(d[0]) flag=0;if(flag==0) break;d[0]=-inf;sort(d,d+l,cmp);}if(flag) printf("yes\n");else printf("no\n");}return 0;}6.KRUSKAL#include<iostream>#include<algorithm>using namespace std;int u[15005],v[15005],w[15005],fath[15005],r[15005];int ans1[15005],ans2[15005];bool cmp(int i,int j){return w[i]<w[j];}int find(int x){return fath[x]==x?x:fath[x]=find(fath[x]);}int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++) fath[i]=i;for(int i=1;i<=m;i++) r[i]=i;for(int i=1;i<=m;i++){cin>>u[i]>>v[i]>>w[i];}sort(r+1,r+m+1,cmp);int maxn=0,ans=0,k=0;for(int i=1;i<=m;i++){int e=r[i];int x=find(u[e]),y=find(v[e]);if(x!=y){ans+=w[e];fath[x]=y;if(w[e]>maxn) maxn=w[e];ans1[k]=u[e];ans2[k++]=v[e];}}return 0;}7.prime求最小生成树语法：prim(Graph G,int vcount,int father[]);参数：G：图，用邻接矩阵表示vcount：表示图的顶点个数father[]：用来记录每个节点的父节点返回值：null注意：常数max_vertexes 为图最大节点数常数infinity为无穷大源程序：#define infinity 1000000#define max_vertexes 5typedef int Graph[max_vertexes][max_vertexes];void prim(Graph G,int vcount,int father[]){int i,j,k;intlowcost[max_vertexes],closeset[max_vertexes],used[max_vertexes]; for (i=0;i<vcount;i++){lowcost[i]=G[0][i];closeset[i]=0;used[i]=0;father[i]=-1;}used[0]=1;for (i=1;i<vcount;i++){j=0;while (used[j]) j++;for (k=0;k<vcount;k++)if ((!used[k])&&(lowcost[k]<lowcost[j])) j=k;father[j]=closeset[j];used[j]=1;for (k=0;k<vcount;k++)if (!used[k]&&(G[j][k]<lowcost[k])){ lowcost[k]=G[j][k];closeset[k]=j; }}}8.Dijkstra语法：result=Dijkstra(Graph G,int n,int s,int t, int path[]); 参数：G：图，用邻接矩阵表示n：图的顶点个数s：开始节点t：目标节点path[]：用于返回由开始节点到目标节点的路径返回值：最短路径长度注意：输入的图的权必须非负顶点标号从0 开始用如下方法打印路径：i=t;while (i!=s){printf("%d<--",i+1);i=path[i];}printf("%d\n",s+1);源程序：int Dijkstra(Graph G,int n,int s,int t, int path[]){int i,j,w,minc,d[max_vertexes],mark[max_vertexes];for (i=0;i<n;i++) mark[i]=0;for (i=0;i<n;i++){ d[i]=G[s][i];path[i]=s; }mark[s]=1;path[s]=0;d[s]=0;for (i=1;i<n;i++){minc=infinity;w=0;for (j=0;j<n;j++)if ((mark[j]==0)&&(minc>=d[j])) {minc=d[j];w=j;}mark[w]=1;for (j=0;j<n;j++)if((mark[j]==0)&&(G[w][j]!=infinity)&&(d[j]>d[w]+G[w][j])){ d[j]=d[w]+G[w][j];path[j]=w; }}return d[t];}9.Bellman-ford语法：result=Bellman_ford(Graph G,int n,int s,int t,int path[],int success);参数：G：图，用邻接矩阵表示n：图的顶点个数s：开始节点t：目标节点path[]：用于返回由开始节点到目标节点的路径success：函数是否执行成功返回值：最短路径长度注意：输入的图的权可以为负，如果存在一个从源点可达的权为负的回路则success=0顶点标号从0 开始用如下方法打印路径：i=t;while (i!=s){printf("%d<--",i+1);i=path[i];}printf("%d\n",s+1);源程序：int Bellman_ford(Graph G,int n,int s,int t,int path[],int success){int i,j,k,d[max_vertexes];for (i=0;i<n;i++) {d[i]=infinity;path[i]=0;}d[s]=0;for (k=1;k<n;k++)for (i=0;i<n;i++)for (j=0;j<n;j++)if (d[j]>d[i]+G[i][j]){d[j]=d[i]+G[i][j];path[j]=i;}success=0;for (i=0;i<n;i++)for (j=0;j<n;j++)if (d[j]>d[i]+G[i][j]) return 0;success=1;return d[t];}10. SPFA#include<iostream>#include<cstdio>#include<cstring>#include<vector>using namespace std;const __int64 maxn=1001000;const __int64 inf=1000100000;struct edge//邻接表{__int64 t,w;//s->t=w;__int64 next;//数组模拟指针};__int64 p[maxn],pf[maxn];//邻接表头节点edge G[maxn],Gf[maxn];//邻接表__int64 V,E;//点数[1-n] 边数__int64 dis[maxn];__int64 que[maxn],fro,rear;//模拟队列__int64 vis[maxn];__int64 inque[maxn];//入队次数bool spfa(__int64 s0){fro=rear=0;for(__int64 i=1;i<=V;i++) dis[i]=inf;dis[s0]=0;memset(vis,0,sizeof(vis));memset(inque,0,sizeof(inque));que[rear++]=s0;vis[s0]=1;inque[s0]++;while(fro!=rear){__int64 u=que[fro];fro++;if(fro==maxn) fro=0;vis[u]=0;for(__int64 i=p[u];i!=-1;i=G[i].next){__int64 s=u,t=G[i].t,w=G[i].w;if(dis[t]>dis[s]+w){dis[t]=dis[s]+w;if(vis[t]==0){que[rear++]=t,vis[t]=1;inque[t]++;if(inque[t]>V) return false;if(rear==maxn) rear=0;}}}}return true;}int main(){__int64 ci;scanf("%I64d",&ci);while(ci--){scanf("%I64d%I64d",&V,&E);memset(p,-1,sizeof(p));memset(pf,-1,sizeof(pf)); for(__int64 i=0;i<E;i++){__int64 u,v,w;scanf("%I64d%I64d%I64d",&u,&v,&w);G[i].t=v;G[i].w=w;G[i].next=p[u];p[u]=i;Gf[i].t=u;Gf[i].w=w;Gf[i].next=pf[v];pf[v]=i;}__int64 ans=0;spfa(1);//求第一个点到其他点的最短距离和for(__int64 i=1;i<=V;i++) ans+=dis[i];//反方向再来一次spfa 求其他点到第一个点的最短距离和 for(__int64 i=1;i<=V;i++) p[i]=pf[i];for(__int64 i=0;i<E;i++) G[i]=Gf[i];spfa(1);for(__int64 i=1;i<=V;i++) ans+=dis[i];printf("%I64d\n",ans);}return 0;}11.Kosaraju模板#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100000;struct edge{int t,w;//u->t=w;int next;};int V,E;//点数(从1开始)，边数int p[maxn],pf[maxn];//邻接表原图,逆图edge G[maxn],Gf[maxn];//邻接表原图,逆图int l,lf;void init(){memset(p,-1,sizeof(p));memset(pf,-1,sizeof(pf));l=lf=0;}void addedge(int u,int t,int w,int l){G[l].w=w;G[l].t=t;G[l].next=p[u];p[u]=l;}void addedgef(int u,int t,int w,int lf){Gf[l].w=w;Gf[l].t=t;Gf[l].next=pf[u];pf[u]=l;}///Kosaraju算法,返回为强连通分量个数bool flag[maxn]; //访问标志数组int belg[maxn]; //存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量int numb[maxn]; //结束时间(出栈顺序)标记,其中numb[i]表示离开时间为i的顶点//用于第一次深搜,求得numb[1..n]的值void VisitOne(int cur, int &sig){flag[cur] = true;for (int i=p[cur];i!=-1;i=G[i].next){if (!flag[G[i].t]){VisitOne(G[i].t,sig);}}numb[++sig] = cur;}//用于第二次深搜,求得belg[1..n]的值void VisitTwo(int cur, int sig){flag[cur] = true;belg[cur] = sig;for (int i=pf[cur];i!=-1;i=Gf[i].next){if (!flag[Gf[i].t]){VisitTwo(Gf[i].t,sig);}}//Kosaraju算法,返回为强连通分量个数int Kosaraju_StronglyConnectedComponent(){int i, sig;//第一次深搜memset(flag,0,sizeof(flag));for ( sig=0,i=1; i<=V; ++i ){if ( false==flag[i] ){VisitOne(i,sig);}}//第二次深搜memset(flag,0,sizeof(flag));for ( sig=0,i=V; i>0; --i ){if ( false==flag[numb[i]] ){VisitTwo(numb[i],++sig);}}return sig;}int main(){while(scanf("%d",&V)==1){init();for(int i=1;i<=V;i++){int u=i,t,w=1;while(scanf("%d",&t)==1&&t){E++;addedge(u,t,w,l++);addedgef(t,u,w,lf++);}}int ans=Kosaraju_StronglyConnectedComponent(); printf("%d\n",ans);}return 0;12.tarjan模板//自己模板#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100000;int V,E;//点数(1) 边数struct edge//邻接表{int t,w;//u->t=w;int next;};int p[maxn];//表头节点edge G[maxn];int l;void init(){memset(p,-1,sizeof(p));l=0;}//添加边void addedge(int u,int t,int w,int l)//u->t=w;{G[l].w=w;G[l].t=t;G[l].next=p[u];p[u]=l;}//tarjan算法求有向图强联通分量int dfn[maxn],lowc[maxn];//dfn[u]节点u搜索的次序编号,lowc[u]u或者u的子树能够追溯到的栈中的最早的节点int belg[maxn];//第i个节点属于belg[i]个强连通分量int stck[maxn],stop;//stck栈int instck[maxn];//第i个节点是否在栈中int scnt;//强联通分量int index;void dfs(int i){dfn[i]=lowc[i]=++index;instck[i]=1;//节点i入栈stck[++stop]=i;for(int j=p[i];j!=-1;j=G[j].next){int t=G[j].t;//更新lowc数组if(!dfn[t])//t没有遍历过{dfs(t);if(lowc[i]>lowc[t]) lowc[i]=lowc[t];}//t是i的祖先节点else if(instck[t]&&lowc[i]>dfn[t]) lowc[i]=dfn[t];}//是强连通分量的根节点if(dfn[i]==lowc[i]){scnt++;int t;do{t=stck[stop--];instck[t]=0;belg[t]=scnt;}while(t!=i);}}int tarjan(){stop=scnt=index=0;memset(dfn,0,sizeof(dfn));memset(instck,0,sizeof(instck));for(int i=1;i<=V;i++){if(!dfn[i]) dfs(i);}return scnt;}int main(){while(scanf("%d",&V)==1){init();for(int i=1;i<=V;i++){int x;while(scanf("%d",&x)==1&&x){E++;addedge(i,x,1,l++);}}int ans=tarjan();printf("%d\n",ans);}return 0;}//吉大模板邻接表版#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100000;int V,E;//点数(1) 边数struct edge//邻接表{int t,w;//u->t=w;int next;};int p[maxn];//表头节点edge G[maxn];int l;void init(){memset(p,-1,sizeof(p));l=0;}//添加边void addedge(int u,int t,int w,int l)//u->t=w;{G[l].w=w;G[l].t=t;G[l].next=p[u];p[u]=l;}//tarjan算法求有向图强联通分量int dfn[maxn],lowc[maxn];//dfn[u]节点u搜索的次序编号,lowc[u]u或者u的子树能够追溯到的栈中的最早的节点int stck[maxn],stop;//stck栈int pre[maxn];//int scnt;//强联通分量int cnt;//void dfs(int v)//1-V{int t,minc=lowc[v]=pre[v]=cnt++;stck[stop++]=v;for(int i=p[v];i!=-1;i=G[i].next){int pv=G[i].t;if(pre[pv]==-1) dfs(pv);if(lowc[pv]<minc) minc=lowc[pv]; }if(minc<lowc[v]){lowc[v]=minc;return ;}do{dfn[t=stck[--stop]]=scnt;lowc[t]=V;}while(t!=v);++scnt;}int tarjan(){stop=cnt=scnt=0;memset(pre,-1,sizeof(pre));for(int i=1;i<=V;i++){if(pre[i]==-1) dfs(i);}return scnt;}int main(){while(scanf("%d",&V)==1){init();for(int i=1;i<=V;i++){int x;while(scanf("%d",&x)==1&&x){E++;addedge(i,x,1,l++);}}int ans=tarjan();printf("%d\n",ans);}return 0;}二、数学1．剩余定理int mod(int c[],int b[],int n){int all_multy=1,sum=0;int i,j,x[5];for(i=0;i<n;i++)all_multy*=c[i];for(i=0;i<n;i++)x[i]=all_multy/c[i];for(i=0;i<n;i++){j=1;while((x[i]*j)%c[i]!=1)j++;x[i]*=j;}for(i=0;i<n;i++)sum+=(b[i]*x[i]);return sum%all_multy;}2．N!中质因子P的个数//对于任意质数p，n！中有（n/p+n/p^2+n/p^3+...)个质因子p。

for (i=0; i<l; i++)
{
k=s[i]*m+add;
if (k>=10)
{
s[i]=k%10;
add=k/10;
flag=1;
}
else
{
s[i]=k;
flag=0;
add=0;
}
}
if (flag)
{
l=i+1;
s[i]=add;
}
else l=i;
for (i=0; i<l; i++)
{
p=pr[i-1]*pr[1];
q=pi[i-1]*pi[1];
s=(pr[i-1]+pi[i-1])*(pr[1]+pi[1]);
pr[i]=p-q;
pi[i]=s-p-q;
}
for (it=0; it<=n-2; it=it+2)
{
vr=fr[it];
vi=fi[it];
fr[it]=vr+fr[it+1];
s2[i-j]=c;
}
s2[i+1]='\0';
}
7.最大公约数、最小公倍数
语法：resulet=hcf(int a,int b)、result=lcd(int a,int b)
参数：
a：
int a，求最大公约数或最小公倍数
b：
int b，求最大公约数或最小公倍数
返回值：
返回最大公约数（hcf）或最小公倍数（lcd）
k=k+1;
sum=sum/10;
}
for (i=blen-2;i>=0;i--)

计算几何模板
ACd
1
基础部分 1.几何公式.............................................................................................................................................. 5 1.1 三角形 ....................................................................................................................................... 5 1.2 四边形 ....................................................................................................................................... 5 1.3 正 n 边形 ...................................................................................................................................5 1.4 圆............................................................................................................................................... 5 1.5 棱柱.......................................

三计算模型
规定RAM的原始运算如下： 1）算术运算 2）两个实数之间的比较 3）间接寻址及求根运算，三角函数运算，指 数函数运算，对数函数运算。 执行每种运算耗费一个时间单位。
四常见计算几何基本问题
• 矢量的概念
• • • • • • • • • • • • • • • • • • • • • • • • • • • •
基本问题（续）
• 在实际编程中，没有必要计算所有的交点，首先应判断线段和多边形的边是否内 交，倘若线段和多边形的某条边内交则线段一定在多边形外；如果线段和多边形 的每一条边都不内交，则线段和多边形的交点一定是线段的端点或者多边形的顶 点，只要判断点是否在线段上就可以了。
得出算法如下： if 线端PQ的端点不都在多边形内 then return false; 点集pointSet初始化为空; for 多边形的每条边s do if 线段的某个端点在s上 then 将该端点加入pointSet; else if s的某个端点在线段PQ上 then 将该端点加入pointSet; else if s和线段PQ相交 // 这时候已经可以肯定是内交了 then return false; 将pointSet中的点按照X-Y坐标排序; for pointSet中每两个相邻点 pointSet[i] , pointSet[ i+1] do if pointSet[i] , pointSet[ i+1] 的中点不在多边形中 then return false; return true; 这个过程中的排序因为交点数目肯定远小于多边形的顶点数目n，所以最多是 常数级的复杂度，几乎可以忽略不计。因此算法的时间复杂度也是O(n)。
基本问题（续）
基本问题（续）

}
//计算dot product U ・ V
double dmult(point3 u,point3 v) {
return u. x*v. x+u. y*v. y+u. z*v. z;
}
//矢量差u - V
point3 subt (point3 u,point3 v){
point3 ret;
ret. x=u. x—v. x;
}
int parallel(point3 ul,point3 u2,point3 u3,point3 vl,point3 v2,point3 v3){
return vlen(xmult(pvec(ul, u2, u3), pvec(vl, v2, v3))) <eps;
}
//判直线与平面平行
int parallel(line3 1,plane3 s) {
}
//判四点共面
int dots_onplane(point3 a,point3 b,point3 c,point3 d) { return zero(dmult(pvec(a, b, c), subt(d, a)));
//判点是否在线段上，包括端点和共线int dot_online_in(point3 p,line3 1) {
■
9
}
int same_side(point3 pl, point3 p2, point3 si, point3 s2, point3 s3){
return
dmult (pvec (si,s2,s3), subt(pl, si))*dmult(pvec(si, s2, s3), subt (p2, sl))>eps;
}

#include<bits/stdc++.h>using namespace std;const double eps =1e-8;const double INF =1e20;const double pi = acos ;int dcmp (double x) {if (fabs (x) < eps) return0;return (x <0-1:1);}$inline double sqr (double x) {return x*x;}f %.2f\n", x, y);}bool operator== (const Point &b) const {return (dcmp ==0&& dcmp ==0);}bool operator< (const Point &b) const {return (dcmp ==0 dcmp <0: x < ;}Point operator+ (const Point &b) const {return Point (x+, y+;`}Point operator- (const Point &b) const {return Point , ;}Point operator* (double a) {return Point (x*a, y*a);}Point operator/ (double a) {return Point (x/a, y/a);}double len2 () {f\n", r);；}bool operator== (const Circle &a) const {return p ==&& (dcmp ==0);}double area () {otate_left ());Line v = Line ((b+c)/2, ((b+c)/2) + (c-b).rotate_left ()); Point p = line_intersection (u, v);double r = dis (p, a);return Circle (p, r);}|Circle in_circle (Point a, Point b, Point c) { r -l*l);Point tmp =+ (l);p1 = tmp + ( ().change_len (h));p2 = tmp + ( ().change_len (h));if (rel ==2|| rel ==4) return1;return2;}int line_cirlce_intersection (Line v, Circle u, Point &p1, Point &p2) {hange_len (r1));= q + ( ().change_len (r1));== r1;*return2;}Line u1 = Line + ().change_len (r1), + ().change_len (r1));Line u2 = Line + ().change_len (r1), + ().change_len (r1));Circle cc = Circle (q, r1);Point p1, p2;if (!line_cirlce_intersection (u1, cc, p1, p2))line_cirlce_intersection (u2, cc, p1, p2);c1 = Circle (p1, r1);if (p1 == p2) {c2 = c1;^return1;}c2 = Circle (p2, r1);return2;}int get_circle (Line u, Line v, double r1, Circle &c1, Circle &c2, Circle &c3, Circle &c4) {hange_len (r1), + ().change_len (r1));Line u2 = Line + ().change_len (r1), + ().change_len (r1));Line v1 = Line + ().change_len (r1), + ().change_len (r1));Line v2 = Line + ().change_len (r1), + ().change_len (r1));==== r1;…= line_intersection (u1, v1);= line_intersection (u1, v2);= line_intersection (u2, v1);= line_intersection (u2, v2);return4;}int get_circle (Circle cx, Circle cy, double r1, Circle &c1, Circle &c2) {otate_left ());v = u;return1;}~double d = dis , q);double l =*d;double h = sqrt *- l*l);u = Line (q, + .change_len (l) + .rotate_left ().change_len (h)); v = Line (q, + .change_len (l) + .rotate_right ().change_len (h));return2;}double area_circle (Circle a, Circle v) {" << endl;return res;}/- ;int d2 = dcmp (b[(i+1)%n].y - ;if (k >0&& d1 <=0&& d2 >0)w++;if (k <0&& d2 <=0&& d1 >0)w--;}if (w !=0)return1;return0;—}int convex_cut (Line u, Point *p, int n, Point *po) {//直线切割多边形左侧//返回切割后多边形的数量int top =0;for (int i =0; i < n; i++) {int d1 = dcmp (cross p[i]);int d2 = dcmp (cross p[(i+1)%n]);if (d1 >=0) po[top++] = p[i];if (d1*d2 <0) po[top++] = line_intersection (u, Line (p[i], p[(i+1)%n]));}(return top;}double convex_circumference (Point *p, int n) {//多边形的周长(凹凸都可以)double ans =0;for (int i =0; i < n; i++) {ans += dis (p[i], p[(i+1)%n]);}return ans;}|double area_polygon_circle (Circle c, Point *p, int n) {//多边形和圆交面积double ans =0;for (int i =0; i < n; i++) {int j = (i+1)%n; //cout << i << " " << j << "//" << endl;if (dcmp (cross (p[j], p[i]) >=0)ans += circle_traingle_area (p[i], p[j], c);elseans -= circle_traingle_area (p[i], p[j], c);}return fabs (ans);}<Point centre_of_gravity (Point *p, int n) {//多边形的重心(凹凸都可以) double sum = , sumx =0, sumy =0;Point p1 = p[0], p2 = p[1], p3;for (int i =2; i <= n-1; i++) {p3 = p[i];double area = cross (p2-p1, p3-p2)/;sum += area;sumx +=++*area;sumy +=++*area;p2 = p3;~}return Point (sumx/*sum), sumy/*sum));}int convex_hull (Point *p, Point *ch, int n) {//求凸包//所有的点集凸包点集点集的点数sort (p, p+n);int m =0;for (int i =0; i < n; i++) {while (m >1&& cross (ch[m-1]-ch[m-2], p[i]-ch[m-1]) <=0) m--;ch[m++] = p[i];}int k = m;for (int i = n-2; i >=0; i--) {while (m > k && cross (ch[m-1]-ch[m-2], p[i]-ch[m-1]) <=0) m--;ch[m++] = p[i];}if (n >1)m--;return m;}。

快速排斥试验引申
• 思考： • 简单的改造一下就可以用来判断一个矩形 是否在另一个矩形内部 • NKOJ 1177 rectangles
凸包
• convex hull • 是指对于平面上给定的一些点，选取一个 最小的凸多边形使得这些点或者在其内部， 或者在其边上
求凸包的Graham扫描法
• 对于一个有三个或以上点的点集Q • 令p0为Q中Y-X坐标排序下最小的点 设<p1,p2,...pm>为对其余点按以p0为中心的极角 逆时针排序所得的点集（如果有多个点有相同的 极角，除了距p0最远的点外全部移除） 压p0进栈S，压p1进栈S，压p2进栈S for(i=3;i<=m;++i){ while(由S的栈顶元素的下一个元素、S的栈顶 元素以及pi构成的折线段不拐向左侧){ 对S弹栈 压pi进栈S } } return S
计算几何
需要注意的细节
• 常用头文件#include<math.h> • 计算几何中一般来说使用double型比较频 繁，请注意数据类型的选择，该用实数的 时候就用double，而float容易失去精度。 • 判断double型的x是否为0，应当用x<eps && x>-eps（或者fabs(x)<eps），其中eps 代表某个精度，常常取eps=0.000001，还 有其他类似情况也要注意double类型的精 度问题
需要注意的细节
• 圆周率取3.141592654或者更精确，或者用 acos(-1) • 角度制和弧度制的转换，C/C++中的三角函 数均为弧度制 • 尽量少用除法，开方，三角函数，容易失 去精度。用除法时注意除数不为0
向量及其运算

ACM模板---liang一．高精度计算： ------------------------------------------------------------ 31.高精度加法：----------------------------------------------------------- 31）C++ string类实现：----------------------------------------------- 3 2）字符数组char实现：----------------------------------------------- 32.高精度减法：----------------------------------------------------------- 41）C++ string类实现:------------------------------------------------ 4 2）字符数组char实现:------------------------------------------------ 53.高精度乘法------------------------------------------------------------- 51）字符数组char实现:------------------------------------------------ 5 2）C++ string类实现:------------------------------------------------ 64.高精度阶乘（压缩五位）------------------------------------------------- 65.高精度小数加法--------------------------------------------------------- 7 二．计算几何： -------------------------------------------------------------- 81.线段相交：------------------------------------------------------------- 82.点关于直线的对称点：点：（a,b）,直线：Ax+By+C=0------------------------- 93.求凸包 ---------------------------------------------------------------- 94.多边形面积------------------------------------------------------------ 115.皮克定理：------------------------------------------------------------ 116.三角形： ------------------------------------------------------------- 121）点和三角形的关系------------------------------------------------- 12 2）三角形各种面积算法：--------------------------------------------- 137.两圆相交面积---------------------------------------------------------- 14 三．搜索: ------------------------------------------------------------------ 151.DFS(深度优先、回溯) -------------------------------------------------- 152.BFS(广度优先) -------------------------------------------------------- 16 四．数论： ----------------------------------------------------------------- 171.最大公约数，最小公倍数：---------------------------------------------- 172.欧几里德扩展：-------------------------------------------------------- 173.大数除法求余、快速幂取余：-------------------------------------------- 174.同余： --------------------------------------------------------------- 195.筛素数 --------------------------------------------------------------- 19 五．图论 ------------------------------------------------------------------- 201.并查集： ------------------------------------------------------------- 202.最小生成树：---------------------------------------------------------- 201） Prim算法------------------------------------------------------- 21 2）克鲁斯卡尔算法--------------------------------------------------- 223.最短路径: ------------------------------------------------------------ 231）最短路径dijkstra算法-------------------------------------------- 23 1）Floyd算法（最短路径）------------------------------------------- 284.最大匹配 ------------------------------------------------------------- 295.最大流 --------------------------------------------------------------- 31 六．数据结构 --------------------------------------------------------------- 331.RMQ ------------------------------------------------------------------ 332.树状数组 ------------------------------------------------------------- 351)一维树状数组------------------------------------------------------ 352)二维树状数组------------------------------------------------------ 37 七．各种处理函数 ----------------------------------------------------------- 381.字符串 --------------------------------------------------------------- 381）字符串分解函数strtok-------------------------------------------- 38 八．动态规划 --------------------------------------------------------------- 391.最长公共子序列-------------------------------------------------------- 392.单调递增（递减）最长子序列-------------------------------------------- 403.整数规划：------------------------------------------------------------ 42一．高精度计算：1.高精度加法：1）C++ string类实现：#include<string>void sum(string &a,string b) // a=a+b{ int i,j,k,c,s;while (a.length()>b.length()) b='0'+b;// a,b处理成一样长 while (b.length()>a.length()) a='0'+a;c=0;for (i=a.length()-1; i>=0; i--){ s=a[i]-48+b[i]-48+c;if ( s>9 ) { s=s%10; c=1;} else c=0;a[i]=48+s;}if ( c>0 ) a='1'+a;}2）字符数组char实现：#include<string.h>void add(char a[],char b[])//a=a+b{int i,j,k,sum=0;k=strlen(a)>strlen(b)?strlen(a):strlen(b);a[k+1]=0;for(i=strlen(a)-1,j=strlen(b)-1;i>=0||j>=0;i--,j--,k--){ if(i>=0) sum+=a[i]-'0'; if(j>=0) sum+=b[j]-'0';a[k]=sum%10+'0'; sum/=10;}if(sum) a[0]=sum+'0';else strcpy(a,&a[1]);}2.高精度减法：1）C++ string类实现:#include<string>void f(string &a,string b){int i,j,sum=0;for(i=a.length()-1,j=b.length()-1;i>=0||j>=0;i--,j--){sum+=a[i]-'0'; if(j>=0) sum-=b[j]-'0';if(sum<0) {a[i]=sum+10+'0';sum=-1;}else {a[i]=sum+'0';sum=0;}}if(a[0]=='0') a=&a[1];for(i=0;a[i]=='0'&&i<a.length();i++) ;if(i==a.length()) a="0";}2）字符数组char实现:#include <string.h>void jian(char a[],char b[])//a-=b{int i,j,sum=0;for(i=strlen(a)-1,j=strlen(b)-1;i>=0||j>=0;i--,j--){sum+=a[i]-'0'; if(j>=0) sum-=b[j]-'0';if(sum<0) {a[i]=sum+10+'0';sum=-1;}else {a[i]=sum+'0';sum=0;}}if(a[0]=='0') strcpy(a,&a[1]);for(i=0;a[i]=='0';i++) ;if(i==strlen(a)) strcpy(a,"0");}3.高精度乘法1）字符数组char实现:#include <string.h>void chen(char a[],char b[])//a=a*b{ int i,j,k,l,sum,c[410]={0};l=strlen(a)+strlen(b);for(i=strlen(b)-1;i>=0;i--)for(j=strlen(a)-1,k=i+j+1;j>=0;j--,k--){ sum=(b[i]-'0')*(a[j]-'0')+c[k];c[k]=sum%10;c[k-1]+=sum/10;}for(i=c[0]?0:1,j=0;i<l;i++)a[j++]=(c[i]+'0'); a[j]=0;}2）C++ string类实现:#include<string>void chenn(string &a,string b)//a=a*b{ int i,j,k,l,sum,c[410]={0};l=a.length()+b.length();for(i=b.length()-1;i>=0;i--)for(j=a.length()-1,k=i+j+1;j>=0;j--,k--){ sum=(b[i]-'0')*(a[j]-'0')+c[k];c[k]=sum%10;c[k-1]+=sum/10;}i=c[0]?0:1;while(a.length()<l-i) a=a+'0';for(j=0;i<l;i++)a[j++]=(c[i]+'0');}4.高精度阶乘（压缩五位）#include<iostream>#include<iomanip>using namespace std;int a[10000];int main(void){int i,n,w,up,j;while(cin>>n){for(w=a[0]=i=1;i<=n;i++){ for(j=0,up=0;j<w;j++){a[j]=i*a[j]+up;up=a[j]/100000;a[j]%=100000;}if(up) a[w++]=up;}cout<<a[w-1];for(i=w-2;i>=0;i--)cout<<setfill('0')<<setw(5)<<a[i]; cout<<endl;}}5.高精度小数加法#include<cstring>#include<algorithm>void quw0(char a[]) //去除尾部多余的零 eg: 3.5+3.5=7.0变成 7 { int i;for(i=0;i<strlen(a);i++) //判断有没有小数点if(a[i]=='.') break;if(i!=strlen(a)){i=strlen(a)-1;while(a[i]=='0') {a[i]=0;;i--;}if(a[i]=='.') a[i]=0;;}}void add(char *a,char *b)//a=a+b{int i=0,j=0,la=strlen(a),lb=strlen(b),sum=0;while((a[i]-'.')&&i<la) i++;while((b[j]-'.')&&j<lb) j++;if(i==la) {a[i]='.';la++;};if(j==lb) {b[j]='.';lb++;};while(la-i>lb-j) {b[lb]='0';lb++;}while(lb-j>la-i) {a[la]='0';la++;}if(la<lb) { swap(a,b); swap(la,lb); }a[la+1]=0;b[lb]=0;for(i=la-1,j=lb-1;i>=0;i--,j--){ if(a[i]=='.') {a[i+1]='.';continue;}sum+=a[i]-'0'; if(j>=0) sum+=b[j]-'0';a[i+1]=sum%10+'0'; sum/=10;}if(sum) a[0]=sum+'0';else strcpy(a,&a[1]);quw0(a);//根据题目需要是否保留尾0}二．计算几何：1.线段相交：int xj(point x1,point x2,point x3,point x4)//相交为1,不交为0{if(min(x1.x,x2.x)>max(x3.x,x4.x)||min(x1.y,x2.y)>max(x3.y,x4.y)||min(x3.x,x4.x)>max(x1.x,x2.x)||min(x3.y,x4.y)>max(x1.y,x2.y) )return 0;//不交：矩形排斥实验，最小的>最大的肯定不交int a,b,c,d;a=(x1.x-x2.x)*(x3.y-x1.y)-(x1.y-x2.y)*(x3.x-x1.x);//跨立实验 b=(x1.x-x2.x)*(x4.y-x1.y)-(x1.y-x2.y)*(x4.x-x1.x);c=(x3.x-x4.x)*(x1.y-x3.y)-(x3.y-x4.y)*(x1.x-x3.x);d=(x3.x-x4.x)*(x2.y-x3.y)-(x3.y-x4.y)*(x2.x-x3.x);return a*b<=0&&c*d<=0;}2.点关于直线的对称点：点：（a,b）,直线：Ax+By+C=0#include <stdio.h>int main(){int n;float a,b,A,B,C,a1,b1;scanf("%d\n",&n);while(n--){ scanf("%f %f %f %f %f",&a,&b,&A,&B,&C);int a1=int (a-2*A*(A*a+B*b+C)/(A*A+B*B));int b1=int (b-2*B*(A*a+B*b+C)/(A*A+B*B));printf("%d %d\n",a1,b1);}}3.求凸包//根据题目改动数据类型，数组大小，排序方式#include <algorithm>#define eps 1e-8struct point{int x,y;};point pnt[100003],res[100005];bool operator<( point A,point B )//按y排也可，具体看题目要求{ return A.x < B.x || (A.x == B.x && A.y < B.y); }double mult(point p0,point p1,point p2){ r eturn (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x); }//数组下标从0开始，n是点的个数，选中的点在保存在res数组中，个数是topint graham(point pnt[], int n, point res[])//选中的点在保存在res数组中，个数是top{ int i, len, k = 0, top = 1;sort(pnt, pnt + n); //用cmp可能超时，原因未知if (n == 0) return 0; res[0] = pnt[0];if (n == 1) return 1; res[1] = pnt[1];if (n == 2) return 2; res[2] = pnt[2];for (i = 2; i < n; i++){ while (top && mult(pnt[i], res[top], res[top-1])<=eps) top--;res[++top] = pnt[i];}len = top; res[++top] = pnt[n - 2];for (i = n - 3; i >= 0; i--){ while (top!=len && mult(pnt[i], res[top], res[top-1])<=eps) top--;res[++top] = pnt[i];}return top; // 返回凸包中点的个数}4.多边形面积//点必须是顺时针给出或逆时针给出才可用此法//使用时注意数据类型，和数据大小struct point{int x,y;}a[105];int duo(point a[],int n) //点在数组 a[]中，个数是n{ int i,s=0;for(i=1;i<=n;i++)s+=(a[i-1].x*a[i%n].y-a[i-1].y*a[i%n].x);if(s<0) s=-s;return s;// if(s%2) cout<<s/2<<".5"<<endl; 若为longl long 类型，不要用double// else cout<<s/2<<".0"<<endl;}5.皮克定理：//S=a+b÷2-1//(其中a表示多边形内部的点数,b表示多边形边界上的点数,S表示多边形的面积)#include<cmath>struct point{int x,y;};int gcd(int m,int n){if(n==0) return m;return gcd(n,m%n);}int bian(point a[],int n)//算出点A和点B组成的线段上的点{ int s=0,i;for(i=1;i<=n;i++)s+=gcd(abs(a[i-1].x-a[i%n].x),abs(a[i-1].y-a[i%n].y));return s;}int duo(point a[],int n)//求n边形的面积,注意ans未除2；{int i,s=0;for(i=1;i<=n;i++)s+=(a[i-1].x*a[i%n].y-a[i-1].y*a[i%n].x);if(s<0) s=-s;return s;}6.三角形：1）点和三角形的关系//注意数据类型#include <cmath>struct point{int x,y;};bool operator ==(point A,point B){return A.x==B.x&&A.y==B.y;} int area(point A,point B,point C)//三角形面积，未除2{int s=abs((B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x));return s;}int pan3(point a[],point p) //若点在三角形内（不含边界），返回1；{int sa,sb,sc,s;s=area(a[0],a[1],a[2]);sa=area(a[0],a[1],p);sb=area(a[0],a[2],p);sc=area(a[1],a[2],p);if(sa&&sb&&sc&&s==sa+sb+sc) return 1;if((!sa||!sb||!sc)&&s==sa+sb+sc){if(p==a[0]||p==a[1]||p==a[2]) return 4;//若点在三角形顶点上，返回4。

在边界上情况的特殊判断
◦ 一个避免精度问题的加速方法
Authored by Will, IIIS, THU 2020/1/21
8
预备知识：距离与交点的计算
点的距离计算
◦ 线段，直线 ◦ 圆，多边形
线段相关
◦ 线段距离？ ◦ 线段的交点？
圆相关
◦ 直线与圆的距离与交点 ◦ 点与圆的切点 ◦ 两圆的公切点
计算方法
◦ 类似Monotone Chain O(NlogN)
更一般的性质与问题
◦ 简单正交多边形的正交凸包 ◦ 口袋的面积 ◦ 最小的周长
Authored by Will, IIIS, THU 2020/1/21
16
凸包上的序——凸性
凸包的定向 直线与凸包 矩形覆盖问题 点与凸包 凸包与凸包 凸包上的动态计算问题 凸包的划分问题
◦ 线段的相交测试 ◦ 面积的计算
右手方向与左手方向
Authored by Will, IIIS, THU 2020/1/21
7
预备知识：另一个例子
判断点在多边形内部
◦ 凸多边形 ◦ 简单多边形
射线法——效率高！
◦ 共线的处理？
随机斜率 纵切变换
转角法——优美！
◦ 精度问题？
浅谈一些几何问题
清华大学 交叉信息院 吴翼 Will
Authored by Will, IIIS, THU 2020/1/21
1
前言：计算几何与计算机科学
机械自动控制 地理信息贪测 计算机辅助设计 模式识别
◦ 人脸识别 ◦ 相关图像处理
游戏领域
◦ 碰撞检测 ◦ 光线追踪 ◦ 三维场景渲染

A C M国际大学生程序设计竞赛-计算几何源码(1)凸包/*凸包cug_1038*/#include <stdio.h>#include <stdlib.h>struct point{int x, y;}pp;point p[100005];int stack[100005], top;int dis(point a, point b){return ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }int multi(point b, point c, point a){return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); }void swap(point p[], int s, int t){point tmp;tmp = p[s];p[s] = p[t];p[t] = tmp;}int cmp(const void *a, const void *b){point *c = (point *)a;point *d = (point *)b;double k = multi(*c, *d, pp);if(k < 0) return 1;else if(k == 0 && dis(*c, pp) >= dis(*d, pp)) return 1;else return -1;}void Graham(point p[], int n, int stack[], int &top){int i, u;u = 0;for(i = 1;i < n;i++){if(p[i].y == p[u].y && p[i].x < p[u].x) u = i;else if(p[i].y < p[u].y) u = i;}swap(p, 0, u);pp = p[0];qsort(p + 1, n - 1, sizeof(p[0]), cmp);stack[0] = 0;stack[1] = 1;top = 1;for(i = 2;i < n;i++){while(multi(p[i], p[stack[top]], p[stack[top - 1]]) >= 0){if(top == 0) break;top--;}top++;stack[top] = i;}}int main(){int ca, i, j, n;int area;scanf("%d", &ca);for(i = 1;i <= ca;i++){scanf("%d", &n);for(j = 0;j < n;j++){scanf("%d%d", &p[j].x, &p[j].y);}Graham(p, n, stack, top);area = 0;for(j = 1;j <= top - 1;j++){area += abs(multi(p[stack[0]], p[stack[j]], p[stack[j + 1]])); }printf("%.1lf\n", (double)area / 2);}return 0;}--------------------------------------------------------------------------------------------------------------------- (2)判断两条线段是否相交(平行，不平行)bool isIntersected(TPoint s1, TPoint e1, TPoint s2, TPoint e2){//判断线段是否相交//1.快速排斥试验判断以两条线段为对角线的两个矩形是否相交//2.跨立试验if((max(s1.x, e1.x) >= min(s2.x, e2.x)) &&(max(s2.x, e2.x) >= min(s1.x, e1.x)) &&(max(s1.y, e1.y) >= min(s2.y, e2.y)) &&(max(s2.y, e2.y) >= min(s1.y, e1.y)) &&(multi(s2, e1, s1) * multi(e1, e2, s1) >= 0) &&(multi(s1, e2, s2) * multi(e2, e1, s2) >= 0)) return true;return false;}(3)三角形的外接圆(已知不在同一直线上的三点求经过三点的圆)/*三角形的外接圆pku_1329*/#include <stdio.h>#include <math.h>const double eps = 1e-6;typedef struct TPoint{double x;double y;}TPoint;typedef struct TTriangle{TPoint t[3];}TTriangle;typedef struct TCircle{TPoint centre;double r;}TCircle;double distance(TPoint p1, TPoint p2){//计算平面上两个点之间的距离return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)); }double triangleArea(TTriangle t){//已知三角形三个顶点的坐标，求三角形的面积return fabs(t.t[0].x * t.t[1].y + t.t[1].x * t.t[2].y + t.t[2].x * t.t[0].y- t.t[1].x * t.t[0].y - t.t[2].x * t.t[1].y - t.t[0].x * t.t[2].y) / 2; }TCircle circumcircleOfTriangle(TTriangle t){//三角形的外接圆TCircle tmp;double a, b, c, c1, c2;double xA, yA, xB, yB, xC, yC;a = distance(t.t[0], t.t[1]);b = distance(t.t[1], t.t[2]);c = distance(t.t[2], t.t[0]);//根据S = a * b * c / R / 4;求半径Rtmp.r = a * b * c / triangleArea(t) / 4;xA = t.t[0].x; yA = t.t[0].y;xB = t.t[1].x; yB = t.t[1].y;xC = t.t[2].x; yC = t.t[2].y;c1 = (xA * xA + yA * yA - xB * xB - yB * yB) / 2;c2 = (xA * xA + yA * yA - xC * xC - yC * yC) / 2;tmp.centre.x = -(c1 * (yA - yC) - c2 * (yA - yB)) /((xA - xB) * (yA - yC) - (xA - xC) * (yA - yB));tmp.centre.y = -(c1 * (xA - xC) - c2 * (xA - xB)) /((yA - yB) * (xA - xC) - (yA - yC) * (xA - xB));return tmp;}int main(){TTriangle t;TCircle circle;double c, d, e;while(scanf("%lf%lf%lf%lf%lf%lf", &t.t[0].x, &t.t[0].y,&t.t[1].x, &t.t[1].y, &t.t[2].x, &t.t[2].y) != EOF){circle = circumcircleOfTriangle(t);// printf("%lf %lf %lf\n", circle.centre.x, circle.centre.y, circle.r);if(fabs(circle.centre.x) < eps) printf("x^2");else if(circle.centre.x < 0) printf("(x - %.3lf)^2 + ", -circle.centre.x);else printf("(x + %.3lf)^2 + ", circle.centre.x);if(fabs(circle.centre.y) < eps) printf("y^2 = ");else if(circle.centre.y < 0) printf("(y - %.3lf)^2 = ", -circle.centre.y);else printf("(y + %.3lf)^2 = ", circle.centre.y);printf("%.3lf^2\n", circle.r);c = 2 * circle.centre.x;d = 2 * circle.centre.y;e = circle.centre.x * circle.centre.x +circle.centre.y * circle.centre.y - circle.r * circle.r;printf("x^2 + y^2 ");//if(fabs(c) < eps)if(c < 0) printf("- %.3lfx ", -c);else printf("+ %.3lfx ", c);if(d < 0) printf("- %.3lfy ", -d);else printf("+ %.3lfy ", d);if(e < 0) printf("- %.3lf = 0\n", -e);else printf("+ %.3lf = 0\n", e);printf("\n");}return 0;}(4)三角形的垂心内心重心中垂线/*cug_1011_垂心内心重心中垂线.cpp*/#include <iostream>#include <cmath>using namespace std;const double eps = 1e-6;struct point{double x, y;};void K(){//到三边距离和最短}void L(double a, double b, double c, double A, double B, double C) { //垂线的交点double t1, t2, t3;t1 = c * cos(A) / cos(M_PI / 2 - C);t2 = c * cos(B) / cos(M_PI / 2 - C);t3 = a * cos(C) / cos(M_PI / 2 - A);t1 += t2 + t3;printf("%.3lf\n", t1);}struct TLine{double a, b, c;};TLine lineFromSegment(point p1, point p2){//线段所在直线,返回直线方程的三个系统TLine tmp;tmp.a = p2.y - p1.y;tmp.b = p1.x - p2.x;tmp.c = p2.x * p1.y - p1.x * p2.y;return tmp;}point LineInter(TLine l1, TLine l2){//求两直线得交点坐标point tmp;if(fabs(l1.b) < eps){tmp.x = -l1.c / l1.a;tmp.y = (-l2.c - l2.a * tmp.x) / l2.b;}else{tmp.x = (l1.c * l2.b - l1.b * l2.c) / (l1.b * l2.a - l2.b * l1.a); tmp.y = (-l1.c - l1.a * tmp.x) / l1.b;}return tmp;}double dis(point a, point b){return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}void F(double a, double b, double c, double A, double B, double C){//到三顶点的距离和最短, 费马点/*当三角形最大的顶角小于120度的时候，三角形内一点到三顶点之间的距离最小是与三顶点夹角都成120度的点P当最到顶点大于等于120度，该顶点取最小值补充一下，当三角形的最大角小于120度时，费尔码点在三角形内，作法有多种，可以从任二办向外作等边三角形，联接正三角形的顶点和原三角形的对角，两者的联线即所求。

ACM必做50题的解题-计算几何.txt生活，是用来经营的，而不是用来计较的。

感情，是用来维系的，而不是用来考验的。

爱人，是用来疼爱的，而不是用来伤害的。

金钱，是用来享受的，而不是用来衡量的。

谎言，是用来击破的，而不是用来装饰的。

信任，是用来沉淀的，而不是用来挑战的。

POJ 1113 WALL计算几何，求凸包这题的结果等于这个多边形构成的凸包的周长加上以所给半径为半径的圆的周长步骤如下：1)算法首先寻找最最靠下方的点，如果遇到y坐标相同，则寻找x坐标最小的点firstP2)然后根据所有点相对于firstP的偏角的大小进行排序，遇到偏角相等的，只取距离firstP最远的点(排序利用自己手写的快排)3)然后利用Graham算法求凸包4)最后直接求职#include <iostream>#include <cmath>#define PI 3.1415926#define MAX_N 1000using namespace std;//存储原始输入的坐标值，rad是输入的半径double cord[MAX_N + 2][2], rad;int seq[MAX_N + 2];int stack[MAX_N + 2];int n, top;int firstP;int realN;void swap(int pos1, int pos2){int temp = seq[pos1];seq[pos1] = seq[pos2];seq[pos2] = temp;}int dir(int nodes, int node1, int node2){double x1 = cord[node1][0], y1 = cord[node1][1];double x2 = cord[node2][0], y2 = cord[node2][1];double sx = cord[nodes][0], sy = cord[nodes][1];return (x2 - sx) * (y1 - sy) - (x1 - sx) * (y2 - sy);}double getDist(int node1, int node2){double x1 = cord[node1][0], y1 = cord[node1][1];double x2 = cord[node2][0], y2 = cord[node2][1];double res = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));return res;}int compare(int node1, int node2){double x1 = cord[node1][0], y1 = cord[node1][1];double x2 = cord[node2][0], y2 = cord[node2][1];double sx = cord[firstP][0], sy = cord[firstP][1];double type = dir(firstP, node1, node2);if(type == 0){double dist1 = (x1 - sx) * (x1 - sx) + (y1 - sy) * (y1 - sy);double dist2 = (x2 - sx) * (x2 - sx) + (y2 - sy) * (y2 - sy);if(dist1 > dist2)return -2;else if(dist1 == dist2)return 0;elsereturn 2;}else if(type > 0)return 1;elsereturn -1;}void fastSort(int start, int end){if(start < end){int curPos = start;int posS = start, posE = end + 1;while(true){while(compare(seq[++posS], seq[curPos]) < 0 && posS < end); while(compare(seq[--posE], seq[curPos]) > 0 && posE > start); if(posS < posE)swap(posS, posE);elsebreak;}swap(curPos, posE);fastSort(start, posE - 1);fastSort(posE + 1, end);}}void sortSeq(){int i, s = 0;for(i = 1; i <= n; i++){//最低最左点不参加排序if(i == firstP)continue;seq[++s] = i;}realN = n - 1;fastSort(1, realN);//清理夹角相同但是距离不同的点，只取举例firstP最远的点i = 1;while(i < realN){s = i + 1;//equal angle but smaller distancewhile(s <= realN && compare(seq[i], seq[s]) == -2) {seq[s] = -1; //置为无效s++;}i = s;}}//寻找凸包void findQ(){int nodes, node1, node2, type;top = 0;stack[top++] = firstP;int s = 1;int c = 0;while(c < 2){if(seq[s] != -1){c++;stack[top++] = seq[s];}s++;}for(; s <= realN; s++){if(seq[s] == -1)continue;while(true){nodes = stack[top - 2];node1 = stack[top - 1];node2 = seq[s];type = dir(nodes, node1, node2);if(type >= 0)top--;elsebreak;}stack[top++] = seq[s];}}double getRes(){double totalDist = 0;int lastNode = firstP;int curNode;while(top > 0){curNode = stack[--top];totalDist += getDist(lastNode, curNode);lastNode = curNode;}//totalDist += getDist(lastNode, firstP);totalDist += 2 * PI * rad;return totalDist;}int main(){int i;cin>>n>>rad;int minX = INT_MAX, minY = INT_MAX;for(i = 1; i <= n; i++){cin>>cord[i][0]>>cord[i][1];if((cord[i][1] < minY) || (cord[i][1] == minY && cord[i][0] < minX)){firstP = i;minX = cord[i][0];minY = cord[i][1];}}sortSeq();findQ();double res = getRes();printf("%.0f\n", res);return 0;}POJ1292 Will Indiana Jones Get There?题目大意：英雄Jones现在在位置1，有人在位置2呼救，所以他要过去救他，但是有个条件，他必须在墙上走，其实就是说他只能在图示的线段上走，但是线段间有空隙，所以要用一个长板搭在线段间才能从一个线段到另外一个线段，问怎么找到一个路径使得要使用的长板最小。

之所以推荐计算几何题，是因为，本人感觉ACM各种算法中计算几何算是比较实际的算法，在很多领域有着重要的用途（例如本人的专业，GIS）。

以后若有机会，我会补充、完善这个列表。

计算几何题的特点与做题要领：1.大部分不会很难，少部分题目思路很巧妙2.做计算几何题目，模板很重要，模板必须高度可靠。

3.要注意代码的组织，因为计算几何的题目很容易上两百行代码，里面大部分是模板。

如果代码一片混乱，那么会严重影响做题正确率。

4.注意精度控制。

5.能用整数的地方尽量用整数，要想到扩大数据的方法（扩大一倍，或扩大sqrt2）。

因为整数不用考虑浮点误差，而且运算比浮点快。

一。

点，线，面，形基本关系，点积叉积的理解POJ 2318 TOYS（推荐）/JudgeOnline/problem?id=2318POJ 2398 Toy Storage（推荐）/JudgeOnline/problem?id=2398一个矩形，有被若干直线分成N个格子，给出一个点的坐标，问你该点位于哪个点中。

知识点：其实就是点在凸四边形内的判断，若利用叉积的性质，可以二分求解。

POJ 3304 Segments/JudgeOnline/problem?id=3304知识点：线段与直线相交，注意枚举时重合点的处理POJ 1269 Intersecting Lines/JudgeOnline/problem?id=1269知识点：直线相交判断，求相交交点POJ 1556 The Doors （推荐）/JudgeOnline/problem?id=1556知识点：简单图论＋简单计算几何，先求线段相交，然后再用Dij求最短路。

POJ 2653 Pick-up sticks/JudgeOnline/problem?id=2653知识点：还是线段相交判断POJ 1066 Treasure Hunt/JudgeOnline/problem?id=1066知识点：线段相交判断，不过必须先理解“走最少的门”是怎么一回事。