#include<cmath>#include<cstdio>#include<algorithm>using namespace std;//================= 精度误差 ==============const double eps = 1e-8;int dcmp( double x ){if( fabs(x)<eps)return 0;return x < 0 ? -1: 1;}//================= 点结构 ===============struct pnode{double x,y;pnode( double a=0.0,double b=0.0):x(a),y(b){}// X乘重载double operator ^ (const pnode &b)const{return x*b.y - b.x*y;}pnode operator - ( const pnode &b)const{return pnode( x-b.x, y-b.y);}pnode operator * (const double p)const{return pnode( x*p, y*p );}pnode operator + (const pnode&b)const{return pnode( x+b.x, y+b.y );}bool operator == (const pnode&b)const{return dcmp( x-b.x )== 0 && dcmp( y-b.y )==0;}bool operator < (const pnode&b)const{return x < b.x || ( dcmp( x-b.x )==0 && y<b.y );}bool operator > (const pnode&b)const{return x > b.x || ( dcmp( x-b.x )==0 && y>b.y );}};//================ 线结构 ==============typedef pnode myvec;struct pline{pnode st,ed;//st：起始点 ed：终点myvec vec;//向量pline(){}pline(pnode a,pnode b):st(a),ed(b){vec = pnode(b-a);}};/*x乘:公共起始点p0， V向量p0p1,W向量p0p2cross(v,w) > 0 W向量在 V向量左边*/double cross( pnode p0,pnode p1,pnode p2){return (p1-p0) ^ (p2-p0);}double cross(pline a,pline b){return (a.ed-a.st)^(b.ed-b.st);}/*点乘：dot(v,w) == 二者长度乘积再乘上他们夹角的余弦夹角：从 v 到 w 逆时针旋转的角*/double dot( myvec v,myvec w){return v.x*w.x + v.y*w.y;}double dot( pline a,pline b){return a.vec.x * b.vec.x + a.vec.y * b.vec.y;}//长度double length( pline a){return sqrt(dot(a,a));}//返回夹角弧度值 逆时针为正double angle( pline a,pline b){return acos( dot(a,b)/length(a)/length(b) );/*double acos(double x),x范围在 -1~1 之间返回的是一个数值的反余弦弧度值，其范围是 0~ pi 。例如： acos(1) 返回值是 0*/}//a向量旋转rad弧度 rad>0逆时针myvec rotat(myvec a,double rad){return myvec( a.x*cos(rad)-a.y*sin(rad) , a.x*sin(rad)+a.y*cos(rad));}//矢量三角形面积*2double area2(pnode p0,pnode p1,pnode p2){return cross(p0,p1,p2);}//============= 直线，线段 ============//给定两条直线，求角平分线myvec angle_bisector(pnode p, pline v1, pline v2){double rad = angle(v1, v2);return rotat(v1.vec, dcmp(cross(v1, v2)) * 0.5 * rad);}//判断3点共线bool line_coincide(pnode p1, pnode p2, pnode p3){return dcmp(cross(p1,p2,p3)) == 0;}//判断直线平行bool line_parallel(pline v, pline w){return cross(v, w) == 0;}//判断直线垂直bool line_vertical(pline v, pline w){return dot(v, w) == 0;}//点在直线上的投影点pnode get_line_projection(pnode p, pline line){return line.st + line.vec * (dot(line, pline(line.st,p)) / dot(line, line));}//判断点在线段上, 不包含端点//dcmp(dot())<=0包含端点bool on_segment(pnode p, pline line){return dcmp(cross(p,line.st, line.ed)) == 0 && dcmp(dot(line.st - p, line.ed - p)) <0;}//直线求交点 线判断非平行，非重合//直线 p+tv ，q+tw 有唯一交点，当且仅当cross(v,w)!=0pnode get_line_inter_point(pline v,pline w){pline u (w.st,v.st);double t = cross( w,u )/cross(v,w);return v.st + (v.ed-v.st) * t;}//点到直线的距离//平行四边形面积除以底double dist_to_line( pnode p,pline line ){pline v2 (line.st,p);return fabs( cross(line,v2)/length( line));//如果不区绝对值 得到的是有向距离}//点到线段的距离double dist_to_seg( pnode p ,pline seg){if( seg.st == seg.ed )return length( pline(seg.st,p) );pline v2 (seg.st,p);pline v3 (seg.ed,p);if( dcmp( dot(seg,v2) ) < 0)return length( v2 );elseif( dcmp ( dot(seg,v2)) > 0)return length( v3 );elsereturn fabs( cross(seg,v2) )/length( seg );}//判断 线段 与 直线相交bool seg_inter_line(pline line,pline seg){return ( dcmp( cross( seg.st,line.st,line.ed ) ) * dcmp( cross( seg.ed,line.st,line.ed) ) )<=0;}//判断 线段 与 线段 相交（允许端点在另一条线段上或者重合bool seg_inter_seg(pline a,pline b){returnmax( a.st.x, a.ed.x) >= min( b.st.x, b.ed.x)&&max( b.st.x, b.ed.x) >= min( a.st.x, a.ed.x)&&max( a.st.y, a.ed.y) >= min( b.st.y, b.ed.y)&&max( b.st.y, b.ed.y) >= min( a.st.y, a.ed.y)&&//以上端点判断dcmp(cross( a.st, a.ed, b.st ))*dcmp(cross( a.st, a.ed, b.ed ))<=0&& dcmp(cross( b.st, b.ed, a.st ))*dcmp(cross( b.st, b.ed, a.ed ))<=0;}//两条线段有唯一一个不是端点的公共点//线段规范相交（不允许端点在另一条线段上bool seg_proper_inter_seg(pline a,pline b){double c1 = cross( a.st, a.ed, b.st );double c2 = cross( a.st, a.ed, b.ed );double c3 = cross( b.st, b.ed, a.st );double c4 = cross( b.st, b.ed, a.ed );return dcmp(c1)*dcmp(c2)<0&& dcmp(c3)*dcmp(c4)<0;}//判断线段是否在矩形内，允许线段端点再矩形四条边上//参数（线段，矩形左上角顶点，矩形右下角顶点）bool seg_in_rec(pline seg,double xl,double xr,double yt,double yb){returnseg.st.x >= min(xl,xr) && seg.st.x <= max(xl,xr)&& seg.ed.x >= min(xl,xr) && seg.ed.x <= max(xl,xr)&& seg.st.y >= min(yt,yb) && seg.st.y <= max(yt,yb)&& seg.ed.y >= min(yt,yb) && seg.ed.y <= max(yt,yb);}//多边形面积double polygon_area(pnode*p,int n){double area = 0.0;for( int i = 1;i < n-1 ;++i )area += cross( p[0], p[i], p[i+1]);return area*0.5;}int main(){}
