企业网站模块介绍,企业网站个人备案吗,wordpress warring,媒体发布公司文章目录点和向量及运算直线和线段求解点到直线的距离/点在直线上求解点到线段的距离/点在线段上求解两条线段是否相交求解两直线的交点多边形求解多边形面积求解多边形重心求解判断定点与多边形的位置关系凸包graham扫描法graham扫描法加强版圆求解圆与直线的交点求解圆与圆的…
文章目录点和向量及运算直线和线段求解点到直线的距离/点在直线上求解点到线段的距离/点在线段上求解两条线段是否相交求解两直线的交点多边形求解多边形面积求解多边形重心求解判断定点与多边形的位置关系凸包graham扫描法graham扫描法加强版圆求解圆与直线的交点求解圆与圆的交点求解定点与定圆的切线求解圆公切线pick定理求解圆相交面积欧拉定理(图论)求解最小圆覆盖求解最近点对闵可夫斯基和(Minkowski Sum)欢迎来到——各大模板训练场Segments——判断线段相交Points Within——点与多边形位置Rotational Painting——找重心、求凸包、判断点在线段上Professors task——数据结构(set)维护动态凸包The Great Divide——判断凸包是否相交Area——求凸包求多变形面积pick定理That Nice Euler Circuit——欧拉定理Buried memory——求三角形的外心、最小圆覆盖「ICPC World Finals 2017」机场构建 Airport Construction——求凹凸多边形内的最长线段点和向量及运算
点用坐标表示P(x,y)P(x,y)P(x,y)
向量有大小方向与二维点坐标一一对应P(x,y)P(x,y)P(x,y)
向量的运算
定义向量A(x1,y1),B(x2,y2)A(x_1,y_1),B(x_2,y_2)A(x1,y1),B(x2,y2) 加减A±B(x1±x2,y1±y2)A±B(x_1±x_2,y1±y_2)A±B(x1±x2,y1±y2) 数乘kA(kx1,ky1)kA(kx_1,ky_1)kA(kx1,ky1) 模长∣A∣x12y12|A|\sqrt{x_1^2y_1^2}∣A∣x12y12 角度atan2(y1,x1)\operatorname{atan2}(y_1,x_1)atan2(y1,x1)返回的是弧度制 tanθyx→atan2(y,x)θ\tan\theta\frac{y}{x}\rightarrow \operatorname{atan2}(y,x)\thetatanθxy→atan2(y,x)θ 点积/内积(⋅·⋅)A⋅Bx1x2y1y2A·Bx_1x_2y_1y_2A⋅Bx1x2y1y2 几何意义AAA乘以BBB在AAA上的投影A⋅B∣A∣∣B∣cosθA·B|A||B|\cos\thetaA⋅B∣A∣∣B∣cosθ 若A⋅B0A·B0A⋅B0则两向量垂直000夹角为锐角000为钝角 叉积/外积(×\times×)A×B∣x1y1x2y2∣x1y2−x2y1−B×AA\times B\begin{vmatrix}x_1y_1\\x_2y_2\end{vmatrix}x_1y_2-x_2y_1-B\times AA×B∣∣∣∣x1x2y1y2∣∣∣∣x1y2−x2y1−B×A 与行列式的几何意义联系都表示xoyxoyxoy二维平面上以A,BA,BA,B为邻边的平行四边形的有向面积A×B∣A∣∣B∣sinθA\times B|A||B|\sin\thetaA×B∣A∣∣B∣sinθ 若A×B0A\times B0A×B0则向量A,BA,BA,B共线000说明从BBB转到AAA是顺时针000则从BBB转到AAA是逆时针 旋转把AAA逆时针旋转α\alphaα弧度得到新向量A′AA′ A(x1,y1)r(cosθ,sinθ)⇒A′r(cos(θα),sin(θα))A(x_1,y_1)r(\cos\theta,\sin\theta)\Rightarrow Ar\Big(\cos(\theta\alpha),\sin(\theta\alpha)\Big)A(x1,y1)r(cosθ,sinθ)⇒A′r(cos(θα),sin(θα))r(cosθcosα−sinθsinα,cosθsinαsinθcosα)r(\cos\theta\cos\alpha-\sin\theta\sin\alpha,\cos\theta\sin\alpha\sin\theta\cos\alpha)r(cosθcosα−sinθsinα,cosθsinαsinθcosα)(rcosθcosα−rsinθsinα,rcosθsinαrsinθcosα)(r\cos\theta\cos\alpha-r\sin\theta\sin\alpha,r\cos\theta\sin\alphar\sin\theta\cos\alpha)(rcosθcosα−rsinθsinα,rcosθsinαrsinθcosα)(x1cosα−y1sinα,x1sinαy1cosα)(x_1\cos\alpha-y_1\sin\alpha,x_1\sin\alphay_1\cos\alpha) (x1cosα−y1sinα,x1sinαy1cosα) acos\operatorname{acos}acos接受[−1,1][-1,1][−1,1]的浮点数输出的范围是[0,π][0,\pi][0,π] asin\operatorname{asin}asin接受[−1,1][-1,1][−1,1]的浮点数输出的范围是[−π2,π2][-\frac{\pi}{2},\frac{\pi}{2}][−2π,2π] atan\operatorname{atan}atan接受浮点数输出的范围是[−π2,π2][-\frac{\pi}{2},\frac{\pi}{2}][−2π,2π] atan2\operatorname{atan2}atan2接受两个浮点数y,xy,xy,x坐标输出的范围是[−π,π][-\pi,\pi][−π,π] 点在第一象限[0,π2][0,\frac{\pi}{2}][0,2π]第二象限[π2,π][\frac{\pi}{2},\pi][2π,π]第三象限[−π,−π2][-\pi,-\frac{\pi}{2}][−π,−2π]第四象限[−π2,0][-\frac{\pi}{2},0][−2π,0] struct vec {double x, y;vec(){}vec( double X, double Y ) { x X, y Y; }vec operator ( vec t ) { return vec( x t.x, y t.y ); }vec operator - ( vec t ) { return vec( x - t.x, y - t.y ); }vec operator * ( double t ) { return vec( x * t, y * t ); }double dot( vec t ) { return x * t.x y * t.y; }friend double dot( vec s, vec t ) { return s.x * t.x s.y * t.y; }double cross( vec t ) { return x * t.y - y * t.x; }friend double cross( vec s, vec t ) { return s.x * t.y - s.y * t.x; }double angle() { return atan2( y, x ); }friend double angle( vec t ) { return atan2( t.y, t.x ); }vec rotate( double rad ) { return vec( x * cos( rad ) - y * sin( rad ), x * sin( rad ) y * cos( rad ) ); }friend vec rotate( vec t, double rad ) { return vec( t.x * cos( rad ) - t.y * sin( rad ), t.x * sin( rad ) t.y * cos( rad ) ); }double len() { return sqrt( dot( *this ) ); }
};struct point {double x, y;point(){}point( double X, double Y ) { x X, y Y; }point operator ( vec p ) { return point( x p.x, y p.y ); }vec operator - ( point v ) { return vec( x - v.x, y - v.y ); }
};直线和线段
直线的表示方式 斜率式kxbkxbkxb 优点可以控制xxx的取值来得到线段或者射线 缺点不能表示xcxcxc的直线计算斜率kkk需要除法 一般式axbyc0axbyc0axbyc0 优点可以表示所有的直线a,b,ca,b,ca,b,c不是固定的可以同时扩大缩小 尽量避免除法以提高精度方便用解析几何的方法算东西 缺点参数会多一个线段或者射线不好处理 两点式A,BA,BA,B 优点简单 缺点没有考虑直线上的点的特点 一个点和直线的方向向量 设向量vB−AvB-AvB−A,则直线ABABAB上的点可以表示为AvtAvtAvtttt任取 优点可以表示所有的直线并且通过限制ttt的取值可以得到线段或者射线 如取ttt在0−10-10−1之间得到线段取t0t0t0得到射线
求解点到直线的距离/点在直线上 用解析几何的方法设直线l:axbyc0l:axbyc0l:axbyc0点p(x0,y0)p(x_0,y_0)p(x0,y0)到lll的距离为∣ax0by0c∣a2b2\frac{|ax_0by_0c|}{\sqrt{a^2b^2}}a2b2∣ax0by0c∣ 用叉积的方法 用叉积求出以p2p1p_2p_1p2p1和p2p0p_2p_0p2p0为邻边的平行四边形的面积然后除以底p1p2p_1p_2p1p2的长度 同样通过叉积判断点ppp是否在直线上如果在那么构成的平行四边形就是一条线面积为000
struct line {//直线由一个端点p加上表示方向的向量v表示 point p; vec v;line(){}line( point P, vec V ) { p P, v V; };friend double dis( line l, point p ) {//点p到直线l的距离vec v p - l.p;double s cross( l.v, v );//叉积求出平行四边形的面积 return fabs( s ) / l.v.len();//面积除以底边的长度就是高(距离) }friend bool online( line l, point p ) {//判断点p是否在直线l上 共线叉积面积为0 vec v p - l.p;double s cross( l.v, v );return dcmp( s ) 0;}
};求解点到线段的距离/点在线段上 做垂线垂足落在线段上那么点到线段的距离就是点到线段所在直线的距离 垂足不落在线段上此时点到线段的距离就是点到线段的两个端点的距离中较小的那个 ∠p0p2p1\angle p_0p_2p_1∠p0p2p1是钝角且∠p0p1p2\angle p_0p_1p_2∠p0p1p2是锐角则p0p_0p0到线段p1p2p_1p2p1p2的距离是线段p0p2p_0p_2p0p2的长度
用点积可以求得夹角是否为钝角 ∠p0p1p2\angle p_0p_1p_2∠p0p1p2是钝角且∠p0p2p1\angle p_0p_2p_1∠p0p2p1是锐角则p0p_0p0到线段p1p2p_1p_2p1p2的距离是线段p0p1p_0p_1p0p1的长度
所以必须两个夹角都是锐角才能说明垂足在线段上
double dis( point p1, point p2, point p ) {//点p到线段(p1,p2)的距离 double d1 dot( p - p1, p2 - p1 ), d2 dot( p - p2, p1 - p2 );if( dcmp( d1 ) 0 dcmp( d2 ) 0 ) {line l( p1, p2 - p1 );return dis( l, p );}else if( dcmp( d1 ) 0 ) return len( p - p1 );else return len( p - p2 );
}判断点ppp是否在线段上首先要保证ppp在线段所在直线上然后出现在两个端点中间
用点积判断在线段中间则与两端点形成的向量应该是反向的点积结果应为负
bool onseg( point p1, point p2, point p ) {//判断点p是否在由点p1和点p2构成的线段上 line l( p1, p2 - p1 );if( ! online( l, p ) ) return 0;//首先要先能在ab直线上//在线段ab中间-与两端点形成的向量应该是反向的-点积为负 if( dcmp( dot( p - p1, p - p2 ) ) 0 ) return 1;else return 0;
}求解两条线段是否相交 跨立实验
判断p1,p2p_1,p_2p1,p2是否在直线p3p4p_3p_4p3p4的两侧再判断p3,p4p3,p4p3,p4是否在直线p1p2p_1p_2p1p2的两侧
跨立实验通过叉积求其正负判断出左边还是右边
两点分别引出与直线端点的两向量的叉积应为非负数
可能出现某条线段端点在另一条线段上这种情况下的叉积是000 但是也要排除两条线段共线不交的叉积为000的情况
bool seg_intersect( point p1, point p2, point p3, point p4 ) {
//判断线段(p1,p2)和(p3,p4)是否有交-跨立实验-一线段两端点分居另一线段两方double s1 cross( p2 - p1, p3 - p1 ), s2 cross( p2 - p1, p4 - p1 );double s3 cross( p4 - p3, p1 - p3 ), s4 cross( p4 - p3, p2 - p3 );int ret1 dcmp( s1 ) * dcmp( s2 ), ret2 dcmp( s3 ) * dcmp( s4 );if( ret1 0 || ret2 0 ) return 0;if( ret1 0 ret2 0 ) {if( onseg( p1, p2, p3 ) || onseg( p1, p2, p4 ) ) return 1;//可能交点是两线段的某个端点 else return 0;//共线不交}else return 1;
}求解两直线的交点
定义两直线l:p1t(p2−p1)r:p3s(p4−p3)l:p_1t(p_2-p_1)\qquad r:p_3s(p_4-p_3)l:p1t(p2−p1)r:p3s(p4−p3)
则交点可列等式p1t(p2−p1)p3s(p4−p3)p_1t(p_2-p_1)p_3s(p_4-p_3)p1t(p2−p1)p3s(p4−p3) ⇒t(p2−p1)−s(p4−p3)p3−p1⇒{x:t(x2−x1)−s(x4−x3)x3−x1y:t(y2−y1)−s(y4−y3)y3−y1\Rightarrow t(p_2-p_1)-s(p_4-p_3)p_3-p_1\\ \Rightarrow \begin{cases} x:t(x_2-x_1)-s(x_4-x_3)x_3-x_1\\ y:t(y_2-y_1)-s(y_4-y_3)y_3-y_1\\ \end{cases} ⇒t(p2−p1)−s(p4−p3)p3−p1⇒{x:y:t(x2−x1)−s(x4−x3)x3−x1t(y2−y1)−s(y4−y3)y3−y1
D0∣x2−x1−(x4−x3)y2−y1−(y4−y3)∣−∣x2−x1x4−x3y2−y1y4−y3∣D_0 \begin{vmatrix} x_2-x_1-(x_4-x_3)\\ y_2-y_1-(y_4-y_3)\\ \end{vmatrix}- \begin{vmatrix} x_2-x_1x_4-x_3\\ y_2-y_1y_4-y_3\\ \end{vmatrix} D0∣∣∣∣x2−x1y2−y1−(x4−x3)−(y4−y3)∣∣∣∣−∣∣∣∣x2−x1y2−y1x4−x3y4−y3∣∣∣∣
Dt∣x3−x1−(x4−x3)y3−y1−(y4−y3)∣∣x1−x3x4−x3y1−y3y4−y3∣D_t \begin{vmatrix} x_3-x_1-(x_4-x_3)\\ y_3-y_1-(y_4-y_3)\\ \end{vmatrix} \begin{vmatrix} x_1-x_3x_4-x_3\\ y_1-y_3y_4-y_3\\ \end{vmatrix} Dt∣∣∣∣x3−x1y3−y1−(x4−x3)−(y4−y3)∣∣∣∣∣∣∣∣x1−x3y1−y3x4−x3y4−y3∣∣∣∣
Ds∣x2−x1x3−x1y2−y1y3−y1∣−∣x2−x1x1−x3y2−y1y1−y3∣D_s \begin{vmatrix} x_2-x_1x_3-x_1\\ y_2-y_1y_3-y_1\\ \end{vmatrix}- \begin{vmatrix} x_2-x_1x_1-x_3\\ y_2-y_1y_1-y_3\\ \end{vmatrix} Ds∣∣∣∣x2−x1y2−y1x3−x1y3−y1∣∣∣∣−∣∣∣∣x2−x1y2−y1x1−x3y1−y3∣∣∣∣
u⃗p2−p1(x2−x1,y2−y1)v⃗p4−p3(x4−x3,y4−y3)w⃗p1−p3(x1−x3,y1−y3)\vec{u}p_2-p_1(x_2-x_1,y_2-y_1)\\ \vec{v}p_4-p_3(x_4-x_3,y_4-y_3)\\ \vec{w}p_1-p_3(x_1-x_3,y_1-y_3) up2−p1(x2−x1,y2−y1)vp4−p3(x4−x3,y4−y3)wp1−p3(x1−x3,y1−y3)
{D0−u⃗×v⃗Ds−u⃗×w⃗Dtw⃗×v⃗\begin{cases} D_0-\vec{u}\times\vec{v}\\ D_s-\vec{u}\times\vec{w}\\ D_t\vec{w}\times\vec{v}\\ \end{cases} ⎩⎪⎨⎪⎧D0−u×vDs−u×wDtw×v
tDtD0v⃗×w⃗u⃗×v⃗sDsD0u⃗×w⃗u⃗×v⃗t\frac{D_t}{D_0}\frac{\vec{v}\times\vec{w}}{\vec{u}\times\vec{v}}\\ s\frac{D_s}{D_0}\frac{\vec{u}\times\vec{w}}{\vec{u}\times\vec{v}}\\ tD0Dtu×vv×wsD0Dsu×vu×w
注意当且仅当D00D_00D00时方程可能有多解直线重合/ 可能无解直线平行
否则可以根据ttt和sss的取值判断交点是否在线段上
point line_intersect( line l, line r ) {//求交点vec v l.p - r.p;//\vec{w}double s cross( l.v, r.v );//l.v-\vec{u};r.v-\vec{v}if( dcmp( s ) ! 0 ) {//两直线不重合double t cross( r.v, v ) / s;return l.p l.v * t;}else return l.p;
}多边形
用多边形的顶点集合表示顶点顺序不同对应的多边形可能会不同 也可以按极角的规律顺序
求解多边形面积 凸多边形 对凸多边形做三角剖分然后求每个三角形的面积 三角形面积两个向量的叉积表示夹成的平行四边形的面积除以222就是三角形的面 凹多边形 计算出△ABC\triangle ABC△ABC的面积 计算出凹四边形ABCDABCDABCD的面积实际上是△ACD−△ABC\triangle ACD-\triangle ABC△ACD−△ABC 计算出复杂五边形ABCDEABCDEABCDE的面积实际上是四边形ABCD−△ADEABCD-\triangle ADEABCD−△ADE PSPSPS这个五边形不是简单多边形简单多边形是由边不交的线段组成的多边形这里AEAEAE和BCBCBC相交了不妨设交点是GGG 那么这里算的面积实际上是凹四边形GCDEGCDEGCDE的面积减去△AGB\triangle AGB△AGB的面积 计算出凹六边形ABCDEFABCDEFABCDEF的面积实际上是五边形ABCDE△AEFABCDE\triangle AEFABCDE△AEF 实际上这种剖分方法已经不再适用于凹多边形了
其实只需要搞清楚什么时候加三角形面积什么时候减三角形面积
发现ACACAC在ABABAB右边所以减ADADAD在ACACAC左边所以加.........
用叉积算出有向面积求和即可简单多边形的面积就是多个三角形的有向面积和
甚至可以不用多边形上的顶点随便选一个点进行三角剖分都可以 double area( vector point polygon ) {//计算多边形面积 多边形由所有端点集合表示double s 0; int n polygon.size();for( int i 0;i n;i )s ( polygon[i] - point( 0, 0 ) ).cross( polygon[( i 1 ) % n] - point( 0, 0 ) );return fabs( s / 2 );
}求解多边形重心 重心公式(x1x2x33,y1y2y33)(\frac{x_1x_2x_3}{3},\frac{y_1y_2y_3}{3})(3x1x2x3,3y1y2y3) 多边形的重心并不是顶点坐标平均数当然如果所有质量都在顶点上那么这个公式就是正确的
但是显然多边形是质量分布均匀的
同样的把多边形进行三角剖分把每个三角形的质量放到三角形重心处大小为三角形有向面积求加权平均数
point center( vector point polygon ) {double s 0; int n polygon.size(); point p( 0, 0 );for( int i 0;i n;i ) {double t ( polygon[i] - point( 0, 0 ) ).cross( polygon[( i 1 ) % n] - point( 0, 0 ) );s t;p.x ( polygon[i].x polygon[( i 1 ) % n].x ) * t;p.y ( polygon[i].y polygon[( i 1 ) % n].y ) * t;}p.x / 3, p.x / s, p.y / 3, p.y / s;return p;
}求解判断定点与多边形的位置关系
点恰好在多边形边上可以通过枚举多边形的边特判掉剩下来只需要考虑位置在内外 射线法 从定点随机射出一条引向无穷远点的射线根据射线与多边形的交点个数判断位置 如果交点为偶数则在多边形外否则在多边形内 证明显然如果是在外面那么射入多边形就必定伴随着射出多边形多边形是个封闭图形产生偶数个交点
bool inpolygon_line( point p, vector point polygon ) {//射线法判断点p是否在多边形内 int n polygon.size();double r ( rand() / double( RAND_MAX ) - 0.5 ) * 2 * M_PI;//随机一条射线 vec v( cos( r ), sin( r ) );bool ans 0;for( int i 0;i n;i ) {if( onseg( polygon[i], polygon[( i 1 ) % n], p ) ) return 1;//特判点在多边形边上if( inangle( polygon[i] - p, polygon[( i 1 ) % n] - p, v ) ) ans ^ 1;}return ans;
}转角法 沿多边形走一圈累计绕点旋转了多少角度 000点在多边形外 ±π±π±π点在多边形上 ±2π±2π±2π点在多边形内 缺点角度计算要用反三角函数精度不高速度较慢 然则在实现中不可能花费时间精度去真的求角度判定 非常巧妙得利用多边形定点编号自带顺序分辨定点的位置特点结合代码观图解 点III点LLL 所有点都在其下方/上方根据yyy永远不可能触发d0d0的条件程序判定正确 点KKK点JJJ 因为多边形自带顶点顺序满足ccc条件时ddd条件恰好与ififif语句相反程序判定正确 点MMM CD→\overrightarrow{CD}CD满足i1i1i1在iii左边且i1i1i1在点下方iii在点上方cnt-- FG→\overrightarrow{FG}FG满足i1i1i1在iii右边且i1i1i1在点上方iii在点下方cnt 程序判定正确 关键点在于因为多边形自带顶点顺序且封闭所以当点在多边形外的时候如果点(竖直位置)在一条边的中间那么必定会有另外一条反向边含有点 有可能多边形是锯齿图/波浪图多次触发也一定是成对的 bool inpolygon_rad( point p, vector point polygon ) {int n polygon.size(), cnt 0;for( int i 0;i n;i ) {if( onseg( polygon[i], polygon[( i 1 ) % n], p ) ) return 1;double c cross( polygon[i] - p, polygon[( i 1 ) % n] - p );double d1 polygon[i].y - p.y, d2 polygon[( i 1 ) % n].y - p.y;if( c 0 d1 0 d2 0 ) cnt ;if( c 0 d2 0 d1 0 ) cnt --;//c0:p与i1构成的线在p与i构成的线左边(需要p与i的线逆时针旋转)}return cnt ! 0;
}改进的转角法 把被测点看成坐标原点对多边形的一条边Pi−Pi1P_i-P_{i1}Pi−Pi1有四种情况 Pi1P_{i1}Pi1在PiP_iPi的相同象限弧度不变 Pi1P_{i1}Pi1在PiP_iPi的下一象限弧度加π2\frac{\pi}{2}2π Pi1P_{i1}Pi1在PiP_iPi的上一象限弧度减π2\frac{\pi}{2}2π Pi1P_{i1}Pi1在PiP_iPi的相对象限计算向量OPi→\overrightarrow{OP_i}OPi和OPi1→\overrightarrow{OP_{i1}}OPi1的叉积MSMSMS MS0MS0MS0点在多边形上MS0MS0MS0弧度加π\piπMS0MS0MS0弧度减π\piπ 实现时需特判点在边上的情况判断象限的时候000看成正数 原始转交法的几何原理就是此时的跨象限 bool inpolygon_Rad( point p, vector point polygon ) {int n polygon.size(), cnt 0;vector vec v;for( int i 0;i n;i )v.push_back( polygon[i] - p );for( int i 0;i n;i ) {vec v1 v[i], v2 v[( i 1 ) % n ];double c cross( v1, v2 );if( c 0 dot( v1, v2 ) 0 ) return 1;int d1 quadrant( v1 ), d2 quadrant( v2 );if( d2 ( d1 1 ) % 4 ) cnt ;if( d2 ( d1 3 ) % 4 ) cnt --;if( d2 ( d1 2 ) % 4 ) {if( c 0 ) cnt 2;else if( c 0 ) cnt - 2;}}return cnt;
}对于凸多边形 还可以利用叉积判断定点逆时针绕多边形转一圈都在边的左边则定点在多边形内
凸包
定义将最外层的点连接起来构成的凸多边形能包含点集中所有的点
形象上理解就是用橡皮筋撑到无穷大然后放手最后橡皮筋蹦到挂住的点围成的多边形
性质
凸包内任意两点构成的线段都被包含于凸包内凸包是凸多边形凸包的交仍是凸包nnn个点形成的凸包大小在完全随机的情况下期望不大
graham扫描法
类似于斜率优化维护凸壳 先找出算法开始点p0p_0p0——左下点先找最下面的点若有多个最下面点则选择最左的一个点 然后对每个点进行极角排序极角相同的距离点近的在前面 极角点与极轴的夹角 极轴过原点的水平线xxx轴 先把p0,p1,p2p_0,p_1,p_2p0,p1,p2入栈 把点C,D,IC,D,IC,D,I入栈 按极角排序枚举点 先枚举GGG 看D−I−GD-I-GD−I−G发现III左拐到GGG把GGG入栈 如果III右拐或者不变方向到GGG就把III弹栈 在左边还是右边的判断通过叉积可得 然后枚举FFF I−G−FI-G-FI−G−F不转向将GGG弹栈D−I−FD-I-FD−I−F左转不弹III停止将FFF入栈 接着枚举HHH I−F−HI-F-HI−F−H右转将FFF弹栈D−I−HD-I-HD−I−H左转保留停止将HHH入栈 再枚举EEE I−H−EI-H-EI−H−E左转将EEE入栈 考虑AAA H−E−AH-E-AH−E−A右转弹EEEI−H−AI-H-AI−H−A左转保留停止入栈AAA 最后是BBB H−A−BH-A-BH−A−B左转入栈整个程序结束
时间复杂度O(nlogn)O(n\log n)O(nlogn)瓶颈在排序
point Po[maxn], sta[maxn], p[maxn];
int graham() {for( int i 0;i n;i ) p[i] Po[i];int o 0;for( int i 1;i n;i )if( p[i].y p[o].y || ( p[i].y p[o].y p[i].x p[o].x ) ) o i;swap( p[o], p[0] );//p[0]是起点 不参与排序 所以从p1开始sort( p 1, p n, []( point s, point t ) {vec v1 s - p[0], v2 t - p[0];double c cross( v1, v2 );return dcmp( c ) 0 || ( dcmp( c ) 0 dcmp( v1.dot() - v2.dot() ) 0 );} );sta[0] p[0], sta[1] p[1]; int top 1;for( int i 2;i n;i ) {while( top dcmp( cross( sta[top] - sta[top - 1], p[i] - sta[top - 1] ) ) 0 ) top --;sta[ top] p[i];}return top 1;
}缺点如果要保留凸包边上的点则刚才的极角排序就不适用了
如果只有在向右拐的时候才弹栈直走的时候不弹栈也不能保留凸包边上所有的点
e.g. 先A,B,CA,B,CA,B,C入栈然后DDD入栈此时遇到AF,AEAF,AEAF,AE极角相同按距离先排FFFC−D−FC-D-FC−D−F左转FFF入栈D−F−ED-F-ED−F−E右转结果最后EEE被弹出栈了
如果规定极角相同离远点小则FFF活BBB亡总归是顾此失彼
graham扫描法加强版 把对所有点进行的极角排序改造按xxx排序 前两个点p0,p1p_0,p_1p0,p1入栈 枚举后面每个点 如果栈内元素个数111设栈顶toptoptop栈顶下一个lstlstlst 考虑lst−top−pilst-top-p_ilst−top−pi是否向左拐 右拐或者直走都弹栈顶直到向左拐或只剩下一个栈顶将pip_ipi入栈 操作后得到点集的下凸壳 把极角排序后的点倒过来做一遍得到点集的上凸壳
e.g. 所有点排序 先把点1,21,21,2入栈 222弹栈333进栈 444进栈 444出栈555进栈 555出栈666进栈 666出栈777进栈 888进栈 888出栈999进栈 999出栈101010进栈 111111进栈 111111出栈121212进栈 121212出栈131313进栈 141414进栈 得到下凸壳 同理倒序枚举扫描找出上凸壳凸包刻画成功
实际上以yyy作为第一关键字排序先求右半凸包再求左半凸包也一样
如果叉积为000即不改变方向时不弹栈就可以保留凸包边上的点
point Po[maxn], p[maxn], sta[maxn];
int GraHam( int n ) {for( int i 0;i n;i ) p[i] Po[i];sort( p, p n, []( point s, point t ) { return s.x t.x ? s.y t.y : s.x t.x; } );int top 0;for( int i 0;i n;i ) {while( top 1 cross( sta[top - 1] - sta[top - 2], p[i] - sta[top - 2] ) 0 )top --;sta[top ] p[i];}int t top;for( int i n - 2;~ i;i -- ) {while( top t cross( sta[top - 1] - sta[top - 2], p[i] - sta[top - 2] ) 0 )top --;sta[top ] p[i];}if( n 1 ) return top - 1;//倒着求凸包的时候多放了个1点进去else return top;
}更重要的区别在于加强版是根据坐标排序而极角排序显然会带来更大的误差
所以还是选择维护上下凸壳的加强版更优亲身体验UVA-10256 the great divide
圆
圆的表示圆心CCC和半径rrr
圆的一般方程形式(x−x0)2(y−y0)2r2(x-x_0)^2(y-y_0)^2r^2(x−x0)2(y−y0)2r2
已知圆心角表示圆上一点(x0rcosθ,y0rsinθ)(x_0r\cos\theta,y_0r\sin\theta)(x0rcosθ,y0rsinθ)
求解圆与直线的交点
判定相交
算出圆心到直线的距离ddd
drdrdr一个交点drdrdr不相交drdrdr两个交点 求解交点
算出垂足DDD已知直线ABABAB可得ADADAD直线方向向量从AAA点走方向向量长度ddd
∣CD∣∣BD∣r2−d2|CD||BD|\sqrt{r^2-d^2}∣CD∣∣BD∣r2−d2
利用BCBCBC直线的方向向量同理找到所有交点坐标
求解圆与圆的交点
判定相交圆心距d≤r1r2d\le r_1r_2d≤r1r2 求解交点 联立方程求解 几何法 已知∣AC∣,∣AB∣,∣BC∣|AC|,|AB|,|BC|∣AC∣,∣AB∣,∣BC∣余弦定理可求∠BCAα\angle BCA\alpha∠BCAα CACACA直线已知可求得CACACA直线的单位方向向量ca→\overrightarrow{ca}ca 将ca⃗\vec{ca}ca逆时针/顺时针旋转α\alphaα从CCC开始走长度∣BC∣|BC|∣BC∣的向量
求解定点与定圆的切线
切线数量
点在圆内无点在圆上111条点在圆外222条
求解切线 数学解析法 点(x0,y0)(x_0,y_0)(x0,y0)在圆(x−a)2−(y−b)2r2(x-a)^2-(y-b)^2r^2(x−a)2−(y−b)2r2的切线解析式为(x0−a)2(y0−b)2r2(x_0-a)^2(y_0-b)^2r^2(x0−a)2(y0−b)2r2 几何法 已知∣AC∣d,∣AB∣r|AC|d,|AB|r∣AC∣d,∣AB∣r勾股定理求得∣BC∣|BC|∣BC∣长度 余弦定理可解∠BCAα\angle BCA\alpha∠BCAα又知直线CACACA方向向量 逆时针/顺时针旋转α\alphaα得CBCBCB直线方向向量从CCC出发走长度∣BC∣|BC|∣BC∣
求解圆公切线
公切线数量判定
重合d0d0d0无数条内含0dr2−r10dr_2-r_10dr2−r1000条内切dr2−r1dr_2-r_1dr2−r1111条相交r2−r1dr2r1r_2-r_1dr_2r_1r2−r1dr2r1222条外切dr1r2dr_1r_2dr1r2111条外离r1r2dr_1r_2dr1r2d222条外公切线222条内公切线
求解公切线 重合内含不用求 内切/外切的一条内/外公切线对应的是过唯一交点的切线 两条公切线 已知∣AC∣d,∣AD∣r1,∣CE∣r2|AC|d,|AD|r_1,|CE|r_2∣AC∣d,∣AD∣r1,∣CE∣r2垂足为D,ED,ED,E 相似求解FAFCADCEFDFE\frac{FA}{FC}\frac{AD}{CE}\frac{FD}{FE}FCFACEADFEFD∣AF∣,∣FD∣,∣DE∣|AF|,|FD|,|DE|∣AF∣,∣FD∣,∣DE∣长度可得 余弦定理得∠AFD\angle AFD∠AFD CACACA直线已知从AAA出发走ca⃗\vec{ca}ca长度∣AF∣|AF|∣AF∣得到两外公切线交点FFF 逆时针/顺时针旋转相同角度α\alphaα走一定长度得到与圆的交点两点确定一条直线 内切线同理
pick定理
点阵中顶点在格点上的多边形面积公式2S2ab−22S2ab-22S2ab−2
其中aaa表示多边形内部的点数bbb表示多边形边界上的点数SSS表示多边形的面积 一般是反过来使用求aaa
SSS多边形面积可以用叉积解决
边界上的点数bbb用gcd\gcdgcd解决求和枚举多边形的边一边两点的横纵坐标差的最大公约数111
设线段(x1,y1)−(x2,y2)⇒cntgcd(∣x2−x1∣,∣y2−y1∣)1(x_1,y_1)-(x_2,y_2)\Rightarrow cnt\gcd(|x_2-x_1|,|y_2-y_1|)1(x1,y1)−(x2,y2)⇒cntgcd(∣x2−x1∣,∣y2−y1∣)1 pick定理扩展一条线段下方有多少顶点 等价于求∑x0n⌊axbc⌋\sum_{x0}^n\lfloor\frac{axb}{c}\rfloor∑x0n⌊caxb⌋ 求解圆相交面积 #include bits/stdc.h
using namespace std;
#define eps 1e-10double pi acos( -1.0 );int dcmp( double x ) {return fabs( x ) eps ? 0 : ( x 0 ? 1 : -1 );
}struct point {double x, y;point(){}point( double X, double Y ) { x X, y Y; }friend double dis( point p1, point p2 ) { return sqrt( ( p1.x - p2.x ) * ( p1.x - p2.x ) ( p1.y - p2.y ) * ( p1.y - p2.y ) ); }
};struct circle {point o; double r;circle(){}circle( point O, double R ) { o O, r R; }
};double area_circle( circle c1, circle c2 ) {double d dis( c1.o, c2.o );if( dcmp( d - c1.r - c2.r ) 0 ) return 0; //外切或外离if( dcmp( d - fabs( c1.r - c2.r ) ) 0 ) { //内切或内含 double r min( c1.r, c2.r );return pi * r * r;}//相交double rad1 acos( ( c1.r * c1.r d * d - c2.r * c2.r ) / ( 2 * c1.r * d ) ); double rad2 acos( ( c2.r * c2.r d * d - c1.r * c1.r ) / ( 2 * c2.r * d ) );return rad1 * c1.r * c1.r rad2 * c2.r * c2.r - c1.r * d * sin( rad1 );
}欧拉定理(图论)
设GGG为任意联通的平面图nnn表示顶点数mmm表示边数rrr表示面数去除封闭面后剩下的“背景”也算完整的一面
有n−mr2n-mr2n−mr2恒成立 求解最小圆覆盖
平面上有一些点用半径最小的圆覆盖这些点用随机增量法
定义CiC_iCi为覆盖前iii个点的最小包围圆 pi∈Ci−1p_i\in C_i-1pi∈Ci−1则CiCi−1C_iC_{i-1}CiCi−1 pi∉Ci−1p_i\notin C_{i-1}pi∈/Ci−1时的处理需要对CiC_iCi另外更新要求CiC_iCi覆盖点集{p1,p2,…,pi}\{p_1,p_2,…,p_i\}{p1,p2,…,pi} 先让Ci{p1,pi}C_i\{p_1,p_i\}Ci{p1,pi}逐个判断点{p2,p3,…,pi−1}\{p_2,p_3,…,p_{i-1}\}{p2,p3,…,pi−1} 如果存在pj∉Cip_j\notin C_ipj∈/Ci则Ci{pj,pi}C_i\{p_j,p_i\}Ci{pj,pi} 同时再依次判断点{p1,p2,…,pj−1}\{p_1,p_2,…,p_{j-1}\}{p1,p2,…,pj−1}如果存在pk∉Cip_k\notin C_ipk∈/Ci 则Ci{pk,pj,pi}C_i\{p_k,p_j,p_i\}Ci{pk,pj,pi} 因为三点唯一确定一个圆所以只需在此基础上判断其他的点是否位于圆内不停地更新pkp_kpk 当kkk的循环完成时退出循环更新pjp_jpj 当jjj的循环结束时退出循环更新pip_ipi 当ininin时算法完成
从算法直观上来看强烈意识感觉这是个假算法
可能会有这样的问题ABCABCABC三点构成一个圆现在加入DDD点假如DDD不在◯ABC\bigcirc ABC◯ABC内
那么按照算法DDD要在新构造的圆上
先枚举AAAADADAD构成圆的直径假如BBB不在◯AD\bigcirc AD◯AD内让BDBDBD构成圆的直径假如AAA不在◯BD\bigcirc BD◯BD内让ABDABDABD构成一个圆假如CCC不在◯ABD\bigcirc ABD◯ABD内让CDCDCD构成圆的直径假如AAA不在◯CD\bigcirc CD◯CD内让ACDACDACD构成一个圆假如BBB不在◯ACD\bigcirc ACD◯ACD内让BCDBCDBCD构成一个圆
这里出现了直觉上的问题有没有AAA不在◯BCD\bigcirc BCD◯BCD内的可能
事实上是没有的
根据以上描述平面上四个点ABCDABCDABCD任意三个点作圆另外一个点都不在作出的圆内 设ABCDABCDABCD是凹四边形 那么对这个凹四边形求凸包得到三角形 一定存在一个点在另外三个点构成的三角形内部或者边上 点在三角形内那么点自然在三角形的外接圆内 设ABCDABCDABCD是凸四边形 假设四点共圆那么对角和为180∘180^\circ180∘ 如果某个点在此圆外 由四边形的内角和为360∘360^\circ360∘一组对角和小于180∘180^\circ180∘另外一组对角和大于180∘180^\circ180∘ 真正的圆必定是会被枚举到大于此圆的此时又将某个点包含在圆内了 所以极限边界就是四点共圆
必然存在一个点在另外三个点形成的圆内
因此算法流程走完后必定求得最小圆覆盖
时间复杂度
前iii个点在包围◯Ci\bigcirc C_i◯Ci上也就333个点所以点iii在◯Ci\bigcirc C_i◯Ci上不在◯Ci−1\bigcirc C_{i-1}◯Ci−1内的概率是很低的只有3i\frac{3}{i}i3
所以对于iii需要枚举jjj的概率是3i\frac{3}{i}i3
对于jjj需要枚举k的概率也是3j\frac{3}{j}j3
总的复杂度是线性的当然这是建立在点随机排序的情况下最坏还是O(n3)O(n^3)O(n3)的
#define eps 1e-12int dcmp( double x ) {return fabs( x ) eps ? 0 : ( x 0 ? 1 : -1 );
}struct point {double x, y;point(){}point( double X, double Y ) { x X, y Y; }friend double len( point s, point t ) { return sqrt( ( s.x - t.x ) * ( s.x - t.x ) ( s.y - t.y ) * ( s.y - t.y ) ); }point operator ( point p ) { return point( x p.x, y p.y ); }point operator / ( double k ) { return point( x / k, y / k ); }double operator - ( point p ) { return x * x y * y - p.x * p.x - p.y * p.y; }
}p[maxn];double X( point p1, point p2 ) {return p1.x - p2.x;
}double Y( point p1, point p2 ) {return p1.y - p2.y;
}point get_c( point p1, point p2, point p3 ) {double t 2 * ( Y( p2, p1 ) * X( p3, p1 ) - Y( p3, p1 ) * X( p2, p1 ) );return point( ( Y( p2, p1 ) * ( p3 - p1 ) - Y( p3, p1 ) * ( p2 - p1 ) ) / t, ( X( p3, p1 ) * ( p2 - p1 ) - X( p2, p1 ) * ( p3 - p1 ) ) / t );
}int n; point c; double r;
void circle_cover() {random_shuffle( p 1, p n 1 );c p[1], r 0;for( int i 2;i n;i )if( dcmp( len( c, p[i] ) - r ) 0 ) {c p[i], r 0;for( int j 1;j i;j )if( dcmp( len( c, p[j] ) - r ) 0 ) {c ( p[i] p[j] ) / 2, r len( c, p[i] );for( int k 1;k j;k )if( dcmp( len( c, p[k] ) - r ) 0 )c get_c( p[i], p[j], p[k] ), r len( c, p[i] );}}
}求解最近点对
平面上有n个点求最近点对
分治 对点按xxx坐标排序作一条竖线xmidxmidxmid把点集分成两半LLL和RRR 假设现在已经求出LLL的最近点对距离dld_ldlRRR的最近点对距离drd_rdr 最后的答案要么是dmin(dl,dr)d\min(d_l,d_r)dmin(dl,dr)要么是一个LLL中的点和一个RRR中的点的最短距离 考虑LLL中的点和RRR中的点的最短距离如何求 首先LLL中的点xdmidxdmidxdmid的点肯定不行把可行的点记作L′LL′ 同理RRR中的点xmiddxmiddxmidd的点肯定不行把可行的点记作R′RR′ 设PL′⋃R′PL\bigcup RPL′⋃R′ 简单想法就暴力枚举PPP中的点对更新答案但可能PPP中的点数也很多最坏还是O(n2)O(n^2)O(n2) 把PPP中的点按照yyy排序 取定PPP中的点pip_ipi枚举到pjp_jpj使得ypj1−ypi≥dy_{p_{j1}}-y_{p_i}\ge dypj1−ypi≥d就不枚举了 看上去貌似仍然是O(n2)O(n^2)O(n2)事实上并不是只需要枚举O(n)O(n)O(n)次 因为LLL和RRR中的任意两点距离均≥d\ge d≥d 所以在重复点去掉的情况下 对于任意pip_ipi满足ypj−ypidy_{p_{j}}-y_{p_i} dypj−ypid的点只有常数个
闵可夫斯基和(Minkowski Sum)
给定点集A,BA,BA,B它们的闵可夫斯基和ABABAB被定义为{ab∣a∈A,b∈B}\bigg\{ab\bigg|a\in A,b\in B\bigg\}{ab∣∣∣∣a∈A,b∈B}
可以理解为八其中一个图形沿着另外一个图形的边做平移得到的新图形 考虑两个凸包的闵可夫斯基和
由于结果也是一个凸包所以结果集合的这些边也有极角序
并且结果集合上的边都来自于A,BA,BA,B两个凸包上的边
相当于对A,BA,BA,B两个凸包上的边根据极角序做归并排序就是闽可夫斯基和
先对A,BA,BA,B两个凸包按照极角序排序
一般来说A,BA,BA,B两个凸包的点都是逆时针顺序的
所以只需要循环位移A,BA,BA,B两个凸包上的点线性的把yyy坐标最小的点移到最前面就可以了
然后在A,BA,BA,B两个凸包有序的情况下归并得到ABABAB
假设现在做到AiA_iAi和BjB_jBj两个点把AiBjA_iB_jAiBj放入集合用叉积比较Ai1−Ai,Bj1−BjA_{i1}-A_i,B_{j1}-B_jAi1−Ai,Bj1−Bj的极角序极角序较小的指针111如果相同则都111 可能会有三点共线的情况只需要丢进去来一遍求凸包即可
vec v1[maxn], v2[maxn];
point PoA[maxn], PoB[maxn];int minkowski( int n, int m, point *Po ) {for( int i 0;i n;i )v1[i] PoA[( i 1 ) % n] - PoA[i];for( int i 0;i m;i )v2[i] PoB[( i 1 ) % m] - PoB[i];Po[0] PoA[0] PoB[0];int i 0, j 0, cnt 1;while( i n j m ) {if( dcmp( cross( v1[i], v2[j] ) ) 0 )Po[cnt] Po[cnt - 1] v1[i ], cnt ;elsePo[cnt] Po[cnt - 1] v2[j ], cnt ;}while( i n ) Po[cnt] Po[cnt - 1] v1[i ], cnt ;while( j m ) Po[cnt] Po[cnt - 1] v2[j ], cnt ;return cnt;
} 闵可夫斯基和也可以用来求解凸包间的最短距离
在两个凸包内分别任意取两个点a,ba,ba,b这两个点作差得到d→a−b\overrightarrow{d}a-bda−b 那么由a,ba,ba,b的任意性对于所有a,ba,ba,b对d→\overrightarrow{d}d取最小值就是答案把BBB凸包的点全部取反(横纵坐标取相反数)得到B′BB′计算闽可夫斯基和AB′ABAB′实际上计算的是A−BA-BA−B然后计算点(0,0)(0,0)(0,0)到凸包A−BA-BA−B的最短距离即可 求定点到凸包的最短距离 枚举凸包的边求点到线段的距离参考动态凸包的方法以凸包内一点为原点进行极角排序二分找到目标线段求距离 欢迎来到——各大模板训练场
Segments——判断线段相交
problem
如果所有线段在某条直线上的投影有交点那么从这个交点引出一条垂直于直线的线必定交于所有线段
把垂直的线稍微掰一掰直到恰好穿过两个端点
所以枚举任意两个端点引出一条直线判断这直线是否与所有线段相交即可
两个端点可能原来就隶属于统一线段但一定不能是同一个点
#include cstdio
#include cmath
using namespace std;
#define eps 1e-8
#define maxn 105struct point {double x, y;point() {}point( double X, double Y ) { x X, y Y; }point operator ( point t ) { return point( x t.x, y t.y ); }point operator - ( point t ) { return point( x - t.x, y - t.y ); }friend double cross( point s, point t ) { return s.x * t.y - s.y * t.x; }double dot( point t ) { return x * t.x y * t.y; }double len() { return sqrt( dot( *this ) ); }
};struct line {point s, t;line(){}line( point S, point T ) { s S, t T; }
}Line[maxn];int dcmp( double x ) {return fabs( x ) eps ? 0 : ( x 0 ? 1 : -1 );
}bool intersect( line l, line r ) {return dcmp( cross( l.s - r.s, l.t - r.s ) ) * dcmp( cross( l.s - r.t, l.t - r.t ) ) 0;
}int T, n;bool check( line l ) {if( ! dcmp( ( l.t - l.s ).len() ) ) return 0;for( int i 1;i n;i )if( ! intersect( l, Line[i] ) ) return 0;return 1;
}int main() {scanf( %d, T );again :while( T -- ) {scanf( %d, n );for( int i 1;i n;i ) {double lx, ly, rx, ry;scanf( %lf %lf %lf %lf, lx, ly, rx, ry );Line[i] line( point( lx, ly ), point( rx, ry ) );}for( int i 1;i n;i )for( int j i;j n;j )if( check( line( Line[i].s, Line[j].s ) ) || check( line( Line[i].s, Line[j].t ) ) || check( line( Line[i].t, Line[j].s ) ) || check( line( Line[i].t, Line[j].t ) ) ) {printf( Yes!\n );goto again;}printf( No!\n );}return 0;
}Points Within——点与多边形位置
problem
模板判断点是否在多边形内部
#include cmath
#include ctime
#include cstdio
#include vector
#include iostream
#include algorithm
using namespace std;
#define eps 1e-8int dcmp( double x ) {return fabs( x ) eps ? 0 : ( x 0 ? 1 : -1 );
}struct vec {double x, y;vec(){}vec( double X, double Y ) { x X, y Y; }friend double cross( vec s, vec t ) { return s.x * t.y - s.y * t.x; }friend double dot( vec s, vec t ) { return s.x * t.x s.y * t.y; }
};struct point {double x, y;point(){}point( double X, double Y ) { x X, y Y; }vec operator - ( point t ) { return vec( x - t.x, y - t.y ); }
};struct line {point p; vec v;line(){}line( point P, vec V ) { p P, v V; }friend bool online( line l, point p ) { return dcmp( cross( l.v, p - l.p ) ) 0; }
};vector point polygon;bool onseg( point p1, point p2, point p ) {line l( p1, p2 - p1 );if( ! online( l, p ) ) return 0;else if( dcmp( dot( p - p1, p - p2 ) ) 0 ) return 1;else return 0;
}bool inangle( vec v1, vec v2, vec v ) {if( dcmp( cross( v1, v2 ) ) 0 ) swap( v1, v2 );return cross( v1, v ) 0 cross( v2, v ) 0;
}bool inpolygon( point p ) {int n polygon.size(), ans 0;double r ( rand() / double( RAND_MAX ) - 0.5 ) * 2 / M_PI;vec v( cos( r ), sin( r ) ); for( int i 0;i n;i ) {if( onseg( polygon[i], polygon[( i 1 ) % n], p ) ) return 1;if( inangle( polygon[i] - p, polygon[( i 1 ) % n] - p, v ) ) ans ^ 1;}return ans;
}
int main() {int n, m, T 1;while( scanf( %d, n ) n ) {scanf( %d, m );polygon.clear();for( int i 1;i n;i ) {double x, y;scanf( %lf %lf, x, y );polygon.push_back( point( x, y ) );}if( T ! 1 ) printf( \n );printf( Problem %d:\n, T ), T ;while( m -- ) {double x, y;scanf( %lf %lf, x, y );point p( x, y );if( inpolygon( p ) ) printf( Within\n );else printf( Outside\n );}}return 0;
}Rotational Painting——找重心、求凸包、判断点在线段上
problem
先找到重心然后求凸包枚举凸包上的线段判断重心垂足是否落在线段上
#include cmath
#include cstdio
#include vector
#include algorithm
using namespace std;
#define maxn 50005
#define eps 1e-10int dcmp( double x ) {return fabs( x ) eps ? 0 : ( x 0 ? 1 : -1 );
}struct vec {double x, y;vec(){}vec( double X, double Y ) { x X, y Y; }vec operator ( vec v ) { return vec( x v.x, y v.y ); }vec operator - ( vec v ) { return vec( x - v.x, y - v.y ); }vec operator * ( double k ) { return vec( x * k, y * k ); }double dot() { return x * x y * y; }friend double dot( vec u, vec v ) { return u.x * v.x u.y * v.y; }friend double cross( vec u, vec v ) { return u.x * v.y - u.y * v.x; }
};struct point {double x, y;point(){}point( double X, double Y ) { x X, y Y; }vec operator - ( point p ) { return vec( x - p.x, y - p.y ); };point operator ( vec v ) { return point( x v.x, y v.y ); }friend double cross( point s, point t ) { return s.x * t.y - s.y * t.x; }
};struct line {point p; vec v;line(){}line( point P, vec V ) { p P, v V; }
};vector point polygon;
int T, n;point center() {double s 0; point p( 0, 0 );for( int i 0;i n;i ) {double t cross( polygon[i], polygon[( i 1 ) % n] );s t;p.x ( polygon[i].x polygon[( i 1 ) % n].x ) * t;p.y ( polygon[i].y polygon[( i 1 ) % n].y ) * t;}p.x / 3, p.x / s, p.y / 3, p.y / s;return p;
}bool check( point p1, point p2, point p ) {return dcmp( dot( p - p1, p2 - p1 ) ) 0 dcmp( dot( p - p2, p1 - p2 ) ) 0;
}point Po[maxn], sta[maxn], p[maxn];int graham() {for( int i 0;i n;i ) p[i] Po[i];int o 0;for( int i 1;i n;i )if( p[i].y p[o].y || ( p[i].y p[o].y p[i].x p[o].x ) ) o i;swap( p[o], p[0] );sort( p 1, p n, []( point s, point t ) {vec v1 s - p[0], v2 t - p[0];double c cross( v1, v2 );return dcmp( c ) 0 || ( dcmp( c ) 0 dcmp( v1.dot() - v2.dot() ) 0 );} );sta[0] p[0], sta[1] p[1]; int top 1;for( int i 2;i n;i ) {while( top dcmp( cross( sta[top] - sta[top - 1], p[i] - sta[top - 1] ) ) 0 ) top --;sta[ top] p[i];}return top 1;
}int main() {scanf( %d, T );while( T -- ) {scanf( %d, n );polygon.clear();for( int i 0;i n;i ) {double x, y;scanf( %lf %lf, x, y );Po[i] point( x, y );polygon.push_back( Po[i] );}point c center();int m graham(), ans 0;for( int i 0;i m;i )if( check( sta[i], sta[( i 1 ) % m], c ) ) ans ;printf( %d\n, ans );}return 0;
}Professor’s task——数据结构(set)维护动态凸包
problem
#include set
#include cmath
#include cstdio
using namespace std;
#define int long longstruct point {int x, y, dis;double rad;point(){}point( int X, int Y ) { x X, y Y; }point operator ( point p ) { return point( x p.x, y p.y ); }point operator - ( point p ) { return point( x - p.x, y - p.y ); }friend int cross( point s, point t ) { return s.x * t.y - s.y * t.x; }
}Po[5], o;bool operator ( const point s, const point t ) { return s.rad t.rad || ( s.rad t.rad s.dis t.dis );
}set point s;
#define it set point :: iteratorit left( it i ) {if( i s.begin() ) i s.end();i --;return i;
}it right( it i ) {i ;if( i s.end() ) i s.begin();return i;
}int dis( point p ) {return ( p.x - o.x ) * ( p.x - o.x ) ( p.y - o.y ) * ( p.y - o.y );
}int Q;signed main() {scanf( %lld, Q );for( int i 1, x;i 3;i ) {scanf( %lld %lld %lld, x, Po[i].x, Po[i].y );o o Po[i], Po[i].x * 3, Po[i].y * 3;}for( int i 1;i 3;i ) {Po[i].dis dis( Po[i] );Po[i].rad atan2( Po[i].y - o.y, Po[i].x - o.x );s.insert( Po[i] );}Q - 3;int opt, x, y;while( Q -- ) {scanf ( %lld %lld %lld, opt, x, y );x * 3, y * 3;point p( x, y );p.dis dis( p );p.rad atan2( y - o.y, x - o.x );it r s.lower_bound( p );if( r s.end() ) r s.begin();it l left( r );if( opt 1 ) {if( cross( p - point(*l), point(*r) - point(*l) ) 0 ) continue;s.insert( p );it now s.find( p );l left( now ); it lst left( l );while( cross( point(*l) - point(*lst), point(*now) - point(*lst) ) 0 )s.erase( l ), l lst, lst left( lst );r right( now ); it nxt right( r );while( cross( point(*r) - point(*now), point(*nxt) - point(*now) ) 0 )s.erase( r ), r nxt, nxt right( nxt );}else {if( cross( p - point(*l), point(*r) - point(*l) ) 0 ) printf( YES\n );else printf( NO\n );}}return 0;
}The Great Divide——判断凸包是否相交
problem #include bits/stdc.h
using namespace std;
#define eps 1e-10
#define maxn 505int dcmp( double x ) {return fabs( x ) eps ? 0 : ( x 0 ? 1 : -1 );
}struct vec {double x, y;vec(){}vec( double X, double Y ) { x X, y Y; }vec operator ( vec v ) { return vec( x v.x, y v.y ); }vec operator - ( vec v ) { return vec( x - v.x, y - v.y ); }vec operator * ( double k ) { return vec( x * k, y * k ); }double dot() { return x * x y * y; }friend double dot( vec u, vec v ) { return u.x * v.x u.y * v.y; }friend double cross( vec u, vec v ) { return u.x * v.y - u.y * v.x; }
};struct point {double x, y;point(){}point( double X, double Y ) { x X, y Y; }point operator ( vec v ) { return point( x v.x, y v.y ); }vec operator - ( point p ) { return vec( x - p.x, y - p.y ); }
}R[maxn], B[maxn], hallR[maxn], hallB[maxn], p[maxn];struct line {point p; vec v;line(){}line( point P, vec V ) { p P, v V; }friend bool online( line l, point p ) { return dcmp( cross( l.v, p - l.p ) ) 0; }
};bool onseg( point p1, point p2, point p ) {line l( p1, p2 - p1 );if( ! online( l, p ) ) return 0;if( dcmp( dot( p - p1, p - p2 ) ) 0 ) return 1;else return 0;
}bool seg_intersect( point p1, point p2, point p3, point p4 ) {double s1 cross( p2 - p1, p3 - p1 ), s2 cross( p2 - p1, p4 - p1 );double s3 cross( p4 - p3, p1 - p3 ), s4 cross( p4 - p3, p2 - p3 );int ret1 dcmp( s1 ) * dcmp( s2 ), ret2 dcmp( s3 ) * dcmp( s4 );if( ret1 0 || ret2 0 ) return 0;else if( ret1 0 ret2 0 ) {if( onseg( p1, p2, p3 ) || onseg( p1, p2, p4 ) ) return 1;else return 0;} else return 1;
}int graham( int n, point *Po, point *sta ) {for( int i 0;i n;i ) p[i] Po[i];sort( p, p n, []( point s, point t ) { return s.x t.x ? s.y t.y : s.x t.x; } );int top 0;for( int i 0;i n;i ) {while( top 1 cross( sta[top - 1] - sta[top - 2], p[i] - sta[top - 1] ) 0 )top --;sta[top ] p[i];}int t top;for( int i n - 2;~ i;i -- ) {while( top t cross( sta[top - 1] - sta[top - 2], p[i] - sta[top - 1] ) 0 )top --;sta[top ] p[i];}if( n 1 ) top --;return top;
}bool inpolygon_rad( point p, point *polygon, int n ) {int cnt 0;for( int i 0;i n;i ) {if( onseg( polygon[i], polygon[( i 1 ) % n], p ) ) return 1;double c cross( polygon[i] - p, polygon[( i 1 ) % n] - p );double d1 polygon[i].y - p.y, d2 polygon[( i 1 ) % n].y - p.y;if( c 0 d1 0 d2 0 ) cnt ;if( c 0 d2 0 d1 0 ) cnt --;}return cnt ! 0;
}int main() {int n, m;next : while( scanf( %d %d, n, m ) ) {if( ! n ! m ) return 0;for( int i 0;i n;i )scanf( %lf %lf, R[i].x, R[i].y );for( int i 0;i m;i )scanf( %lf %lf, B[i].x, B[i].y );n graham( n, R, hallR );m graham( m, B, hallB );for( int i 0;i n;i )if( inpolygon_rad( R[i], hallB, m ) ) { printf( No\n ); goto next; }for( int i 0;i m;i )if( inpolygon_rad( B[i], hallR, n ) ) { printf( No\n ); goto next; }for( int i 0;i n;i )for( int j 0;j m;j )if( seg_intersect( hallR[i], hallR[( i 1 ) % n], hallB[j], hallB[( j 1 ) % m] ) ) {printf( No\n );goto next;}printf( Yes\n ); }return 0;
}Area——求凸包求多变形面积pick定理
problem
从(0,0)(0,0)(0,0)开始题目给的相当于是nnn个向量帮忙搭建凸包
套用pick定理
#include cmath
#include cstdio
#include vector
using namespace std;struct point {double x, y;point(){}point( double X, double Y ) { x X, y Y; }point operator ( point p ) { return point( x p.x, y p.y ); }friend double cross( point s, point t ) { return s.x * t.y - s.y * t.x; }
};vector point polygon;
int T, n;double area() {double s 0;for( int i 0;i n;i )s cross( polygon[i], polygon[( i 1 ) % n] );return fabs( s );
}int gcd( int x, int y ) {if( ! y ) return x;else return gcd( y, x % y );
}int main() {scanf( %d, T );for( int Case 1;Case T;Case ) {polygon.clear();scanf( %d, n );point p( 0, 0 );polygon.push_back( p );for( int i 1;i n;i ) {double x, y;scanf( %lf %lf, x, y );p p point( x, y );polygon.push_back( p );}if( Case 1 ) printf( \n );printf( Scenario #%d:\n, Case );double s area(); int v 0;for( int i 0;i n;i ) {point p1 polygon[i], p2 polygon[( i 1 ) % n];v gcd( fabs( p1.x - p2.x ), fabs( p1.y - p2.y ) );}printf( %d %d %.1f\n, ( int( s ) 2 - v ) / 2 , v, s / 2 );}return 0;
}That Nice Euler Circuit——欧拉定理
套用欧拉定理注意重合点要删掉
#include cmath
#include cstdio
#include algorithm
using namespace std;
#define eps 1e-9
#define maxn 305int dcmp( double x ) {return fabs( x ) eps ? 0 : ( x 0 ? 1 : -1 );
}struct vec {double x, y;vec(){}vec( double X, double Y ) { x X, y Y; }vec operator * ( double k ) { return vec( x * k, y * k ); }friend double dot( vec u, vec v ) { return u.x * v.x u.y * v.y; }friend double cross( vec u, vec v ) { return u.x * v.y - u.y * v.x; }
};struct point {double x, y;point(){}point( double X, double Y ) { x X, y Y; }point operator ( vec v ) { return point( x v.x, y v.y ); }vec operator - ( point p ) { return vec( x - p.x, y - p.y ); }
}Po[maxn], V[maxn * maxn];struct line {point p; vec v;line(){}line( point P, vec V ) { p P, v V; }
};bool strict_intersect( point p1, point p2, point p3, point p4 ) {double s1 cross( p2 - p1, p3 - p1 ), s2 cross( p2 - p1, p4 - p1 );double s3 cross( p4 - p3, p1 - p3 ), s4 cross( p4 - p3, p2 - p3 );return dcmp( s1 ) * dcmp( s2 ) 0 dcmp( s3 ) * dcmp( s4 ) 0;
}point intersection( line l, line r ) {double s cross( l.v, r.v );if( dcmp( s ) ! 0 ) {double t cross( r.v, l.p - r.p ) / s;return l.p l.v * t;}
}bool operator ( const point p1, const point p2 ) {return p1.x p2.x ? p1.y p2.y : p1.x p2.x;
}bool operator ( const point p1, const point p2 ) {return dcmp( p1.x - p2.x ) 0 dcmp( p1.y - p2.y ) 0;
}bool onseg( point l, point r, point p ) {return dcmp( cross( l - p, r - p ) ) 0 dcmp( dot( l - p, r - p ) ) 0;
}int main() {int n, T 0;while( scanf( %d, n ) n ) {for( int i 0;i n;i )scanf( %lf %lf, Po[i].x, Po[i].y ), V[i] Po[i];n --; int cnt n, E n;for( int i 0;i n;i )for( int j i 1;j n;j )if( strict_intersect( Po[i], Po[i 1], Po[j], Po[j 1] ) )V[cnt ] intersection( line( Po[i], Po[i 1] - Po[i] ), line( Po[j], Po[j 1] - Po[j] ) );sort( V, V cnt );cnt unique( V, V cnt ) - V;for( int i 0;i cnt;i )for( int j 0;j n;j )if( onseg( Po[j], Po[j 1], V[i] ) ) E ;printf( Case %d: There are %d pieces.\n, T, 2 - cnt E );}return 0;
}Buried memory——求三角形的外心、最小圆覆盖
problem
#include bits/stdc.h
using namespace std;
#define maxn 100005
#define eps 1e-12int dcmp( double x ) {return fabs( x ) eps ? 0 : ( x 0 ? 1 : -1 );
}struct point {double x, y;point(){}point( double X, double Y ) { x X, y Y; }friend double len( point s, point t ) { return sqrt( ( s.x - t.x ) * ( s.x - t.x ) ( s.y - t.y ) * ( s.y - t.y ) ); }point operator ( point p ) { return point( x p.x, y p.y ); }point operator / ( double k ) { return point( x / k, y / k ); }double operator - ( point p ) { return x * x y * y - p.x * p.x - p.y * p.y; }
}p[maxn];double X( point p1, point p2 ) {return p1.x - p2.x;
}double Y( point p1, point p2 ) {return p1.y - p2.y;
}point get_c( point p1, point p2, point p3 ) {double t 2 * ( Y( p2, p1 ) * X( p3, p1 ) - Y( p3, p1 ) * X( p2, p1 ) );return point( ( Y( p2, p1 ) * ( p3 - p1 ) - Y( p3, p1 ) * ( p2 - p1 ) ) / t, ( X( p3, p1 ) * ( p2 - p1 ) - X( p2, p1 ) * ( p3 - p1 ) ) / t );
}int n; point c; double r;
void circle_cover() {random_shuffle( p 1, p n 1 );c p[1], r 0;for( int i 2;i n;i )if( dcmp( len( c, p[i] ) - r ) 0 ) {c p[i], r 0;for( int j 1;j i;j )if( dcmp( len( c, p[j] ) - r ) 0 ) {c ( p[i] p[j] ) / 2, r len( c, p[i] );for( int k 1;k j;k )if( dcmp( len( c, p[k] ) - r ) 0 )c get_c( p[i], p[j], p[k] ), r len( c, p[i] );}}
}int main() {while( scanf( %d, n ) n ) {for( int i 1;i n;i )scanf( %lf %lf, p[i].x, p[i].y );circle_cover();printf( %.2f %.2f %.2f\n, c.x, c.y, r );}return 0;
}「ICPC World Finals 2017」机场构建 Airport Construction——求凹凸多边形内的最长线段
source
#include cmath
#include cstdio
#include iostream
#include algorithm
using namespace std;
#define maxn 205
#define double long double
const double eps 1e-7;
int n;
double ans;int dcmp( double x ) {return fabs( x ) eps ? 0 : ( x 0 ? 1 : -1 );
}struct vec {double x, y;vec(){}vec( double X, double Y ) { x X, y Y; }vec operator ( vec v ) { return vec( x v.x, y v.y ); }vec operator - ( vec v ) { return vec( x - v.x, y - v.y ); }vec operator * ( double k ) { return vec( x * k, y * k ); }friend double len( vec v ) { return v.x * v.x v.y * v.y; }friend double dis( vec v ) { return sqrt( len( v ) ); }friend double dot( vec u, vec v ) { return u.x * v.x u.y * v.y; }friend double cross( vec u, vec v ) { return u.x * v.y - u.y * v.x; }friend bool order( vec v ) { return dcmp( v.y ) 0 || ( dcmp( v.y ) 0 dcmp( v.x ) 0 ); }//order规定一种指向 friend bool sameline( vec u, vec v ) { return dcmp( cross( u, v ) ) 0; }//共线判断:两向量同向或反向 叉积面积为0 一维直线在二维的面积为0 friend bool samedirection( vec u, vec v ) { return sameline( u, v ) dcmp( dot( u, v ) ) 0; }//同向判断:首先共线然后点积为非负-锐角
};struct point {double x, y;point(){}point( double X, double Y ) { x X, y Y; }point operator ( point p ) { return point( x p.x, y p.y ); }point operator ( vec v ) { return point( x v.x, y v.y ); }point operator / ( double k ) { return point( x / k, y / k ); }vec operator - ( point p ) { return vec( x - p.x, y - p.y ); }
}polygon[maxn]; struct line {point p; vec v;line(){}line( point P, vec V ) { p P, v V; }
}seg[maxn];bool onseg( point l, point r, point p ) {return dcmp( cross( l - p, r - p ) ) 0 dcmp( dot( l - p, r - p ) ) 0;
}bool onseg( line MS, point p ) {point l MS.p, r MS.p MS.v;return onseg( l, r, p );
}bool inpolygon( point p ) {int cnt 0;for( int i 0;i n;i ) {if( onseg( polygon[i], polygon[( i 1 ) % n], p ) ) return 1;double c cross( polygon[i] - p, polygon[( i 1 ) % n] - p );double d1 polygon[i].y - p.y, d2 polygon[( i 1 ) % n].y - p.y;if( c 0 d1 0 d2 0 ) cnt ;if( c 0 d2 0 d1 0 ) cnt --;}return cnt ! 0;
}point seg_intersect( line l, point p1, point p2 ) {line r( p1, p2 - p1 );return l.p l.v * ( cross( r.v, l.p - r.p ) / cross( l.v, r.v ) );
}point p[maxn];void solve( line MS ) {int cnt 0;for( int i 0;i n;i )if( sameline( MS.v, polygon[( i 1 ) % n] - polygon[i] ) ) continue;//与int main里跳过线段同理 else {point intersection seg_intersect( MS, polygon[i], polygon[( i 1 ) % n] );if( onseg( polygon[i], polygon[( i 1 ) % n], intersection ) ) p[ cnt] intersection;//如果线段与多边形的某些线段有交 记录下来//多边形可能是凹多边形 所以这种情况是可能出现的 }sort( p 1, p cnt 1, []( point s, point t ) { return s.x t.x ? s.y t.y : s.x t.x; } );int l 1;while( l cnt ! onseg( MS, p[l]) ) l ;int r l;while( r cnt onseg( MS, p[r 1] ) ) r ;//两个while确定MS线段的首尾端点都被包含在多边形内 for( int i l;i r;i )if( ! inpolygon( ( p[i] p[i 1] ) / 2 ) ) return;//然后新的整MS线段要被完全包含在多边形内才行 看图while( l 1 inpolygon( ( p[l] p[l - 1] ) / 2 ) ) l --;//然后尽可能的往外拓展 p点是拍了序的 所以可以保证 while( r cnt inpolygon( ( p[r] p[r 1] ) / 2 ) ) r ;ans max( ans, dis( p[r] - p[l] ) );
}int main() {scanf( %d, n );for( int i 0, x, y;i n;i ) {scanf( %d %d, x, y );polygon[i] point( x, y ); }for( int i 0;i n;i ) {int ip 0;for( int j 0;j n;j )if( i j || order( polygon[j] - polygon[i] ) ) continue;else seg[ ip] line( polygon[i], polygon[j] - polygon[i] );sort( seg 1, seg ip 1, []( line l, line r ) {//极角排序建构多边形边集 int c dcmp( cross( l.v, r.v ) );return c 0 || ( c 0 dcmp( len( l.v ) - len( r.v ) ) 0 );} );for( int j 1;j ip;j )if( j 1 sameline( seg[j - 1].v, seg[j].v ) ) continue;/*solve做的操作是把一条线段尽可能地边长撑到多边形边界为止 所以一个直线上的线段做一次就可以了 用共线sameline或者同向samedirection判断都是一样的因为已经极角排序过了-逆时针 */ else solve( seg[j] ); }printf( %.9Lf\n, ans );return 0;
}
