浙江大学ACM模板.pdf

《浙江大学ACM模板.pdf》由会员分享，可在线阅读，更多相关《浙江大学ACM模板.pdf（94页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 Zhejiang University ICPC Team Routine Library by WishingBone（Dec.2002)Last Update（Nov。2004)by Riveria 1、几何.4 1。1 注意.4 1.2 几何公式.4 1。3 多边形.5 1.4 多边形切割.8 1。5 浮点函数.8 1。6 面积.12 1.7 球面.13 1.8 三角形.13 1。9 三维几何.15 1.10 凸包.21 1.11 网格.22 1.12 圆.22 1。13 整数函数.24 2、组合.26 2 2.1 组合公式.26 2.2 排列组合生成.26 2.3 生成 gray

2、码.27 2。4 置换(polya).28 2。5 字典序全排列.28 2。6 字典序组合.28 3、结构.29 3.1 并查集.29 3。2 堆.30 3。3 线段树.31 3.4 子段和.34 3。5 子阵和.35 4、数论.35 4。1 阶乘最后非 0 位.35 4.2 模线性方程组.36 4.3 素数.37 4.4 欧拉函数.38 5、数值计算.38 5。1 定积分计算（Romberg).38 5.2 多项式求根（牛顿法）.40 5。3 周期性方程（追赶法）.41 6、图论-NP 搜索.41 6.1 最大团.41 6.2 最大团(npi+pi-beta;相等应该是 abs(a1-a2）

3、在P0，P2顺时针（0，pi）内 负：逆时针（0，pi）内 0:P0,P1,P0，P2共线,夹角为 0 或 pi 10。误差限缺省使用 1e-8！1.2 几何公式 三角形:1.半周长 P=(a+b+c）/2 2.面积 S=aHa/2=absin(C)/2=sqrt（P（Pa）（P-b）（Pc）3.中线 Ma=sqrt（2(b2+c2）-a2）/2=sqrt(b2+c2+2bccos(A）)/2 4.角平分线 Ta=sqrt(bc(b+c)2-a2）)/(b+c）=2bccos（A/2)/（b+c)5.高线 Ha=bsin(C）=csin（B）=sqrt（b2（a2+b2c2)/(2a)2）6。

4、内切圆半径 r=S/P=asin（B/2)sin（C/2）/sin（B+C）/2）=4Rsin(A/2)sin（B/2）sin(C/2）=sqrt（(P-a）（Pb）(P-c)/P）=Ptan(A/2)tan（B/2)tan(C/2)7.外接圆半径 R=abc/（4S）=a/（2sin(A）=b/（2sin(B）=c/（2sin(C)）四边形:D1，D2 为对角线，M 对角线中点连线,A 为对角线夹角 1.a2+b2+c2+d2=D12+D22+4M2 2。S=D1D2sin（A)/2(以下对圆的内接四边形）3.ac+bd=D1D2 4。S=sqrt（(Pa)(Pb）（Pc)（P-d）),P

5、为半周长 正 n 边形:R 为外接圆半径,r 为内切圆半径 1。中心角 A=2PI/n 2。内角 C=（n2)PI/n 3。边长 a=2sqrt（R2r2）=2Rsin（A/2）=2rtan(A/2）4。面积 S=nar/2=nr2tan(A/2）=nR2sin（A）/2=na2/（4tan（A/2)）圆:1。弧长 l=rA 2。弦长 a=2sqrt（2hrh2)=2rsin(A/2）5 3.弓形高 h=r-sqrt(r2a2/4)=r（1-cos(A/2）)=atan（A/4）/2 4。扇形面积 S1=rl/2=r2A/2 5。弓形面积 S2=(rla（rh）)/2=r2（Asin（A)/2

6、 棱柱:1.体积 V=Ah，A 为底面积，h 为高 2.侧面积 S=lp,l 为棱长,p 为直截面周长 3.全面积 T=S+2A 棱锥：1。体积 V=Ah/3，A 为底面积,h 为高(以下对正棱锥）2.侧面积 S=lp/2，l 为斜高,p 为底面周长 3。全面积 T=S+A 棱台:1。体积 V=（A1+A2+sqrt（A1A2）h/3,A1.A2 为上下底面积，h 为高(以下为正棱台）2.侧面积 S=（p1+p2）l/2，p1.p2 为上下底面周长，l 为斜高 3.全面积 T=S+A1+A2 圆柱：1.侧面积 S=2PIrh 2。全面积 T=2PIr（h+r）3。体积 V=PIr2h 圆锥：1

7、。母线 l=sqrt(h2+r2）2。侧面积 S=PIrl 3。全面积 T=PIr(l+r)4。体积 V=PIr2h/3 圆台:1。母线 l=sqrt(h2+(r1r2)2)2.侧面积 S=PI（r1+r2）l 3。全面积 T=PIr1（l+r1）+PIr2(l+r2）4.体积 V=PI（r12+r22+r1r2)h/3 球：1。全面积 T=4PIr2 2.体积 V=4PIr3/3 球台:1.侧面积 S=2PIrh 2.全面积 T=PI(2rh+r12+r22)3.体积 V=PIh(3（r12+r22）+h2)/6 球扇形：1.全面积 T=PIr(2h+r0），h 为球冠高，r0 为球冠底面半

8、径 2.体积 V=2PIr2h/3 1.3 多边形#include stdlib。h include math.h define MAXN 1000#define offset 10000 define eps 1e8#define zero（x）（(x)0？（x):-（x）eps）#define _sign（x）（x)eps?1：(（x)-eps？2:0）)struct pointdouble x,y；struct linepoint a,b;；6 double xmult(point p1,point p2,point p0）return（p1.x-p0。x）(p2.yp0。y）-(p2.

9、x-p0.x)*（p1.y-p0。y);/判定凸多边形,顶点按顺时针或逆时针给出，允许相邻边共线 int is_convex(int n，point p）int i,s3=1，1，1；for（i=0;ins1|s2；i+）s_sign（xmult(p(i+1)n，p（i+2)%n,pi）=0；return s1s2;/判定凸多边形，顶点按顺时针或逆时针给出,不允许相邻边共线 int is_convex_v2(int n,point p)int i,s3=1,1,1；for(i=0；ins0&s1|s2;i+)s_sign(xmult(p（i+1)n,p（i+2)n，pi）)=0;return

10、s0&s1s2;/判点在凸多边形内或多边形边上,顶点按顺时针或逆时针给出 int inside_convex（point q,int n,point*p）int i,s3=1,1，1；for（i=0;in&s1s2;i+)s_sign（xmult（p（i+1)%n,q,pi）)=0;return s1|s2;/判点在凸多边形内，顶点按顺时针或逆时针给出,在多边形边上返回 0 int inside_convex_v2（point q，int n，point*p）int i，s3=1,1，1;for（i=0;in&s0s1|s2;i+）s_sign（xmult(p(i+1)n，q，pi)）=0；r

11、eturn s0&s1|s2;/判点在任意多边形内，顶点按顺时针或逆时针给出/on_edge 表示点在多边形边上时的返回值，offset 为多边形坐标上限 int inside_polygon(point q，int n,point*p，int on_edge=1)point q2;int i=0，count;while(in）for（count=i=0，q2.x=rand()+offset,q2。y=rand(）+offset;in；i+)if(zero(xmult(q，pi，p(i+1)%n)&(pi.xq。x)(p(i+1)%n.x-q.x)eps&(pi。y-q。y）*（p(i+1）%

12、n。y-q.y)eps）return on_edge;else if（zero（xmult(q,q2,pi）)）break;else if(xmult（q，pi,q2)*xmult（q,p(i+1)%n,q2)-eps&xmult（pi，q,p（i+1)n)xmult（pi,q2，p(i+1)n）-eps）count+;return count&1；inline int opposite_side(point p1,point p2，point l1，point l2）return xmult（l1，p1,l2)*xmult(l1，p2,l2）eps；inline int dot_online

13、_in（point p，point l1，point l2)return zero（xmult(p,l1，l2）（l1。x-p.x)(l2。x-p.x)eps&(l1.y-p.y）（l2.y-p.y）7 eps；/判线段在任意多边形内,顶点按顺时针或逆时针给出，与边界相交返回 1 int inside_polygon（point l1,point l2，int n，point p）point tMAXN,tt；int i,j,k=0;if（！inside_polygon(l1,n,p)|！inside_polygon（l2,n,p）)return 0；for(i=0;ieps)ret.x/=t

14、1,ret。y/=t1;return ret;1.4 多边形切割/多边形切割/可用于半平面交#define MAXN 100 define eps 1e8 define zero（x）(x)0？（x）：(x）)eps）struct pointdouble x,y；;double xmult（point p1，point p2，point p0）return(p1.xp0。x）(p2。yp0。y）-(p2。x-p0。x）(p1。yp0。y）;int same_side(point p1，point p2，point l1，point l2)return xmult（l1,p1,l2）xmult（

15、l1，p2,l2）eps;point intersection（point u1,point u2,point v1,point v2)point ret=u1;double t=(（u1。x-v1。x)(v1。y-v2。y）-(u1。y-v1.y)(v1.x-v2。x)）/(（u1.xu2.x)*（v1。y-v2。y）-(u1。y-u2.y)*(v1。x-v2。x)；ret。x+=（u2。xu1.x）*t；ret.y+=(u2。y-u1。y)*t;return ret；/将多边形沿 l1，l2 确定的直线切割在 side 侧切割，保证 l1,l2,side 不共线 void polygon_

16、cut(int n,point p，point l1,point l2,point side）point pp100;int m=0,i;for(i=0；in;i+)if(same_side(pi，side，l1,l2）ppm+=pi;if(！same_side（pi，p(i+1)n，l1,l2)！(zero（xmult(p i,l1，l2）&zero(xmult（p（i+1)%n，l1，l2）)）)ppm+=intersection(pi，p(i+1)n，l1，l2);for(n=i=0;im;i+)if（！i|！zero（ppi。xppi-1.x)！zero（ppi.y-ppi-1。y）)

17、pn+=ppi；if（zero(pn1.xp0。x）&zero(pn-1。y-p0.y）n;if(n3)n=0；1.5 浮点函数 9/浮点几何函数库#include math。h define eps 1e8 define zero（x）(（x）0？（x）：-(x)eps）struct pointdouble x,y；;struct linepoint a，b;；/计算 cross product(P1P0）x(P2-P0）double xmult（point p1,point p2,point p0)return（p1.xp0.x）（p2。y-p0。y)（p2。xp0。x)(p1.yp0。y

18、）；double xmult(double x1，double y1,double x2，double y2，double x0，double y0）return（x1-x0)*(y2y0）-（x2x0）*（y1-y0）；/计算 dot product(P1-P0)。(P2P0)double dmult(point p1,point p2，point p0)return（p1。x-p0。x)（p2。x-p0。x）+（p1.y-p0.y）（p2。yp0.y)；double dmult（double x1,double y1，double x2,double y2，double x0,double

19、 y0)return（x1-x0)*（x2x0)+(y1y0）(y2y0）；/两点距离 double distance(point p1，point p2）return sqrt（(p1。xp2.x）(p1。xp2。x)+(p1。y-p2。y)(p1。y-p2。y)；double distance（double x1,double y1，double x2，double y2）return sqrt(x1x2）（x1x2）+（y1-y2）(y1-y2）；/判三点共线 int dots_inline（point p1,point p2，point p3)return zero(xmult（p1,

20、p2,p3）);int dots_inline(double x1，double y1,double x2，double y2，double x3，double y3）return zero(xmult(x1，y1，x2,y2，x3,y3)；/判点是否在线段上,包括端点 int dot_online_in（point p，line l)return zero(xmult（p,l。a，l.b)）（l.a。x-p.x)（l。b。xp.x）eps&(l。a。y-p.y)（l.b。y-p.y）eps；int dot_online_in(point p,point l1，point l2)return

21、zero（xmult（p，l1,l2）(l1.xp。x)（l2。xp.x)eps&(l1.yp。y）*（l2。yp.y）eps；int dot_online_in（double x，double y,double x1，double y1，double x2,double y2)return zero(xmult(x，y,x1,y1,x2，y2）)&（x1x）(x2-x)eps&(y1y)*(y2-y）eps；/判点是否在线段上,不包括端点 int dot_online_ex（point p,line l）return dot_online_in（p,l）（!zero(p。x-l.a.x）!z

22、ero(p。yl.a.y)(！zero(p。xl.b.x）|!zero（p。yl。b.y）；int dot_online_ex（point p,point l1，point l2)10 return dot_online_in（p，l1,l2)&(！zero(p。xl1。x)|！zero(p.y-l1.y）&(!zero(p.x-l2.x)!zero(p。y-l2。y）)；int dot_online_ex（double x，double y,double x1，double y1，double x2,double y2)return dot_online_in（x，y，x1，y1，x2,y2

23、)&(!zero（xx1）|！zero（yy1)）&(！zero（x-x2)|！zero（yy2）;/判两点在线段同侧，点在线段上返回 0 int same_side（point p1,point p2,line l)return xmult(l。a,p1，l。b）*xmult（l。a，p2,l。b）eps;int same_side(point p1,point p2，point l1，point l2)return xmult（l1,p1,l2）*xmult(l1,p2,l2）eps;/判两点在线段异侧，点在线段上返回 0 int opposite_side（point p1，point

24、p2，line l）return xmult（l。a，p1，l。b）*xmult（l.a,p2,l.b）eps；int opposite_side（point p1，point p2,point l1，point l2)return xmult(l1,p1，l2）xmult（l1，p2,l2）eps）return distance（p，l1）eps）return distance(p，l.a）distance（p,l。b）?distance（p，l.a):distance(p,l.b)；return fabs（xmult（p,l.a，l.b）/distance（l.a，l。b);double

25、disptoseg（point p，point l1,point l2）point t=p；t.x+=l1.y-l2。y,t。y+=l2。x-l1。x;if（xmult（l1，t，p)*xmult(l2，t,p)eps）return distance(p,l1)distance(p，l2）?distance（p，l1):distance(p,l2)；return fabs（xmult（p，l1，l2)）/distance（l1，l2）；/矢量 V 以 P 为顶点逆时针旋转 angle 并放大 scale 倍 point rotate(point v,point p,double angle，d

26、ouble scale)point ret=p；v.x-=p.x,v.y=p。y;p。x=scale*cos(angle)；p.y=scalesin（angle);ret.x+=v。x*p.x-v.yp.y；ret.y+=v。xp.y+v.yp。x；return ret;1.6 面积 include math。h struct pointdouble x,y；/计算 cross product（P1P0)x（P2P0）double xmult（point p1，point p2,point p0)return(p1.x-p0。x)（p2.yp0。y)(p2.xp0。x)(p1.y-p0。y);

27、double xmult(double x1，double y1，double x2，double y2，double x0,double y0)return(x1-x0)（y2-y0）(x2-x0）*（y1y0）;/计算三角形面积,输入三顶点 double area_triangle(point p1,point p2,point p3）return fabs（xmult(p1，p2，p3)/2；double area_triangle(double x1,double y1,double x2,double y2，double x3,double y3）return fabs（xmult（

28、x1，y1,x2,y2,x3,y3)）/2;/计算三角形面积，输入三边长 double area_triangle(double a，double b，double c)double s=（a+b+c）/2；return sqrt（s(s-a）(s-b)*（sc)）;13 /计算多边形面积，顶点按顺时针或逆时针给出 double area_polygon（int n，point*p)double s1=0,s2=0；int i；for（i=0;in；i+）s1+=p(i+1）%n.ypi。x，s2+=p(i+1)n。yp(i+2)n.x;return fabs(s1-s2)/2;1.7 球面

29、include math.h const double pi=acos（1);/计算圆心角 lat 表示纬度，90=w=90,lng 表示经度/返回两点所在大圆劣弧对应圆心角，0=pi+pi)dlng-=pi+pi;if（dlngpi）dlng=pi+pidlng;lat1*=pi/180，lat2=pi/180；return acos(cos(lat1）cos(lat2)cos（dlng)+sin（lat1）sin（lat2)）；/计算距离，r 为球半径 double line_dist（double r,double lng1，double lat1,double lng2，double

30、lat2）double dlng=fabs（lng1-lng2）pi/180;while（dlng=pi+pi)dlng-=pi+pi;if(dlngpi）dlng=pi+pi-dlng；lat1=pi/180，lat2*=pi/180;return rsqrt（2-2（cos（lat1）*cos(lat2)cos（dlng)+sin(lat1)sin(lat2);/计算球面距离,r 为球半径 inline double sphere_dist（double r,double lng1,double lat1，double lng2,double lat2）return rangle（lng1

31、，lat1,lng2,lat2）；1.8 三角形#include math。h struct pointdouble x，y;struct linepoint a,b；double distance(point p1，point p2）return sqrt（p1。xp2.x）（p1.x-p2。x）+（p1.y-p2。y）*（p1.yp2.y)）；point intersection(line u,line v)point ret=u。a；double t=（u。a。xv.a.x)（v。a.y-v.b。y）-(u.a.yv。a。y）(v.a。xv.b。x)）/（(u。a。xu。b.x）（v.a

32、.y-v。b。y）（u.a。yu。b。y)*(v。a。xv。b.x）);14 ret。x+=（u.b。x-u。a。x)t；ret.y+=(u.b。y-u.a.y）*t；return ret；/外心 point circumcenter(point a，point b,point c）line u,v；u。a。x=（a.x+b.x）/2；u。a。y=(a.y+b。y）/2；u。b。x=u.a.xa.y+b。y;u。b.y=u.a.y+a。xb。x;v。a。x=（a。x+c。x)/2;v。a.y=(a。y+c.y）/2；v.b。x=v。a。x-a。y+c。y;v。b。y=v.a。y+a。x-c。x

33、；return intersection（u，v);/内心 point incenter(point a,point b,point c）line u,v；double m,n；u.a=a;m=atan2(b.y-a.y，b。xa。x);n=atan2（c.y-a.y,c.xa。x)；u.b。x=u.a。x+cos（m+n）/2);u.b。y=u.a.y+sin（(m+n）/2);v。a=b；m=atan2（a.y-b.y,a。xb.x);n=atan2(c.y-b。y，c.xb。x);v.b.x=v.a.x+cos(（m+n)/2）;v。b.y=v。a.y+sin（(m+n)/2);retu

34、rn intersection(u,v）；/垂心 point perpencenter(point a，point b,point c）line u，v;u。a=c；u.b.x=u.a。xa.y+b。y；u.b.y=u.a。y+a。xb。x;v。a=b;v。b。x=v。a.x-a。y+c.y；v。b.y=v.a.y+a.x-c。x;return intersection（u,v);/重心/到三角形三顶点距离的平方和最小的点/三角形内到三边距离之积最大的点 point barycenter(point a,point b，point c)line u，v；u.a。x=(a.x+b.x）/2；u.

35、a.y=（a。y+b.y）/2；u.b=c;v。a。x=（a.x+c.x)/2；15 v.a.y=(a.y+c.y）/2；v.b=b；return intersection(u,v）;/费马点/到三角形三顶点距离之和最小的点 point fermentpoint（point a,point b，point c)point u，v；double step=fabs（a.x)+fabs（a。y）+fabs(b.x）+fabs（b。y）+fabs（c.x）+fabs(c.y）；int i，j，k；u.x=（a。x+b。x+c.x）/3；u.y=（a.y+b。y+c.y)/3；while(step1e

36、10)for(k=0;k10;step/=2,k+)for（i=1;i=1;i+)for（j=-1;j=1；j+）v.x=u.x+step*i;v.y=u。y+step*j；if(distance（u,a）+distance（u,b）+distance(u，c）distance(v，a)+distance（v,b）+distance(v，c)）u=v；return u；1.9 三维几何/三维几何函数库#include#define eps 1e8 define zero（x)（x)0?(x）:(x）)eps）struct point3double x，y,z；struct line3point

37、3 a,b;struct plane3point3 a，b,c；/计算 cross product U x V point3 xmult(point3 u,point3 v)point3 ret;ret.x=u。yv.z-v.y*u。z;ret.y=u。zv.xu。xv。z；ret。z=u.xv.yu。y*v。x；return ret;/计算 dot product U。V double dmult（point3 u，point3 v)return u。x*v。x+u.yv.y+u.z*v。z；/矢量差 U-V point3 subt（point3 u，point3 v)point3 ret;

38、ret。x=u.x-v.x；ret.y=u。y-v.y;ret.z=u。zv.z;return ret;16 /取平面法向量 point3 pvec(plane3 s)return xmult(subt（s.a,s.b），subt(s.b,s。c）);point3 pvec(point3 s1，point3 s2,point3 s3）return xmult(subt（s1，s2)，subt(s2，s3)）;/两点距离，单参数取向量大小 double distance（point3 p1，point3 p2)return sqrt(（p1。xp2.x)（p1.xp2.x)+(p1。yp2。y)

39、(p1.y-p2。y）+(p1.z-p2。z）(p1。zp2。z)）;/向量大小 double vlen(point3 p）return sqrt(p。x*p。x+p。yp.y+p。z*p.z）；/判三点共线 int dots_inline(point3 p1,point3 p2,point3 p3)return vlen(xmult(subt(p1,p2)，subt(p2，p3)）eps;/判四点共面 int dots_onplane(point3 a,point3 b，point3 c,point3 d)return zero（dmult（pvec（a,b，c),subt(d,a)）;/判

40、点是否在线段上,包括端点和共线 int dot_online_in(point3 p，line3 l)return zero(vlen（xmult（subt（p，l。a），subt(p，l.b）)）)（l.a.xp。x）*（l。b。x-p.x)eps （l.a.yp.y)*(l。b.y-p。y)eps&（l。a。z-p.z)*（l.b.zp。z）eps;int dot_online_in（point3 p,point3 l1，point3 l2）return zero（vlen(xmult(subt(p，l1），subt(p,l2）)）)&(l1。x-p.x)（l2.x-p.x）eps&(l1

41、.yp.y）*(l2.yp.y）eps&（l1。zp.z）*(l2.zp。z）eps vlen(xmult(subt（p,s。b)，subt（p，s。c)eps&vlen(xmult（subt（p，s。c),subt（p，s。a)）eps；int dot_inplane_ex(point3 p，point3 s1,point3 s2,point3 s3)return dot_inplane_in(p，s1,s2,s3）&vlen（xmult（subt(p，s1)，subt（p，s2）eps&vlen（xmult(subt(p,s2）,subt(p，s3）eps&vlen（xmult（subt（

42、p,s3）,subt（p,s1）)eps;/判两点在线段同侧,点在线段上返回 0,不共面无意义 int same_side（point3 p1，point3 p2，line3 l）return dmult（xmult(subt(l.a，l。b)，subt(p1,l。b）)，xmult(subt(l。a,l.b）,subt（p2,l.b）)eps;int same_side（point3 p1,point3 p2，point3 l1，point3 l2）return dmult(xmult（subt（l1，l2)，subt(p1,l2)，xmult（subt(l1,l2），subt（p2,l2)

43、）eps；/判两点在线段异侧，点在线段上返回 0,不共面无意义 int opposite_side(point3 p1,point3 p2，line3 l）return dmult（xmult（subt（l。a，l.b）,subt（p1，l.b），xmult(subt（l。a,l.b)，subt（p2，l。b）)）eps;int opposite_side（point3 p1,point3 p2，point3 l1，point3 l2）return dmult(xmult(subt(l1,l2），subt（p1，l2),xmult(subt(l1,l2),subt(p2，l2)eps；int

44、same_side（point3 p1，point3 p2，point3 s1,point3 s2，point3 s3）return dmult(pvec（s1,s2,s3）,subt(p1,s1)*dmult（pvec(s1，s2,s3),subt（p2，s1)）eps;/判两点在平面异侧,点在平面上返回 0 int opposite_side(point3 p1,point3 p2,plane3 s)return dmult(pvec（s），subt（p1,s.a）dmult(pvec（s)，subt(p2,s。a)-eps；int opposite_side（point3 p1，poin

45、t3 p2,point3 s1，point3 s2,point3 s3)return dmult(pvec（s1，s2，s3)，subt(p1，s1）)*dmult(pvec（s1,s2，s3）,subt（p2,s1)）-eps;/判两直线平行 int parallel（line3 u,line3 v)return vlen（xmult（subt(u。a，u。b),subt(v.a，v。b)eps；int parallel(point3 u1,point3 u2，point3 v1，point3 v2)18 return vlen(xmult(subt(u1,u2），subt（v1，v2)）e

46、ps；/判两平面平行 int parallel(plane3 u,plane3 v)return vlen(xmult（pvec（u）,pvec(v)）0？（x）：-（x）eps)struct pointdouble x,y；;/计算 cross product（P1P0)x(P2P0)double xmult（point p1，point p2,point p0）return(p1.xp0.x)(p2。yp0。y)(p2。x-p0.x）（p1。yp0.y);/graham 算法顺时针构造包含所有共线点的凸包，O（nlogn)point p1，p2;int graham_cp（const vo

47、id*a,const void*b)double ret=xmult（*（point)a），*(point*)b),p1)；return zero（ret）?（xmult（*(（point*）a)，(（point*）b)，p2)0？1:-1）：(ret0？1：1);void _graham(int n,point p,int s，point ch)int i，k=0;for(p1=p2=p0，i=1；in；p2.x+=pi.x，p2.y+=pi。y，i+）if（p1。ypi。yeps|（zero(p1.ypi。y)&p1。xpi.x）p1=pk=i；p2.x/=n,p2。y/=n;pk=p0，

48、p0=p1;qsort（p+1,n-1,sizeof(point),graham_cp)；for（ch0=p0，ch1=p1，ch2=p2,s=i=3;i0?(x）：（x）struct pointint x,y；int gcd（int a，int b)return b?gcd（b，a%b）:a；/多边形上的网格点个数 int grid_onedge（int n,point*p）int i，ret=0；for（i=0；in；i+)ret+=gcd(abs（pi。xp(i+1）n。x),abs(pi。yp(i+1）%n.y);return ret；/多边形内的网格点个数 int grid_insi

49、de（int n，point*p）int i,ret=0;for（i=0;in；i+)ret+=p（i+1）%n。y*(pi。x-p(i+2)n.x）;return(abs（ret)-grid_onedge(n,p)）/2+1;1.12 圆#include math.h define eps 1e-8 struct pointdouble x,y；double xmult(point p1，point p2,point p0）return（p1.xp0.x)(p2。yp0。y)-(p2。x-p0。x)*（p1.yp0.y）；double distance(point p1,point p2)r

50、eturn sqrt（(p1.xp2.x)*（p1.x-p2。x）+(p1。yp2。y）*(p1。y-p2.y）);double disptoline(point p，point l1，point l2)return fabs(xmult(p,l1,l2)/distance(l1,l2）;23 point intersection(point u1，point u2,point v1，point v2)point ret=u1；double t=(u1.x-v1。x）（v1。yv2。y)（u1.yv1。y)(v1。xv2.x）)/(u1。x-u2.x）（v1.y-v2。y）-（u1.y-u2.