常用计算几何函数.docx

1、常用计算几何函数#include #include #include #include #include #include #include / hdu 4063 using namespace std;#define inf 100000#define pi acos(-1.0)#define eps 1e-8#define maxn 1500#define sqr(x) ( (x)*(x) )/ double fmaxnmaxn;double dismaxn;int sign(double x) if( x eps;/ hdu 4063 3961 3982 struct point dou

2、ble x,y; point() point(double x,double y):x(x),y(y) void in() scanf(%lf%lf,&x,&y); bool operator =(const point &b)const return sign( x - b.x) = 0 & sign( y - b.y) = 0; ;point pmaxn;struct circle point a; double r; circle() circle(point a,double r):a(a),r(r);circle C30;struct node double x1,x2;node T

3、maxn;bool cmp(node a, node b) if( sign( a.x1 - b.x1) = 0 ) return sign( a.x2 - b.x2) 0; return sign( a.x1 - b.x1) 0;double xmult( point a, point b, point o) return ( a.x - o.x)*( b.y - o.y ) - ( a.y - o.y )*( b.x - o.x );/* 计算两点之间的距离 */double dist( point a, point b) double x = a.x - b.x; double y =

4、a.y - b.y; return sqrt( x*x + y*y);/ 求两条直线的交点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.x - u2.x)*(v1.y - v2.y) - (u1.y - u2.y)*(v1.x - v2.x); ret.x += ( u2.x - u1.x)*t; ret.y += ( u2.y - u1.y)

5、*t; return ret;/* 求两个圆的交点 */int circle_intersect(circle A, circle B, point &ia, point &ib) if (A.a.x = B.a.x & A.a.y = B.a.y) return 5; double dd = dist (A.a, B.a); if ( A.r + B.r + eps dd ) return 1; double k, a, b, d, aa, bb, cc, c, drt; k = A.r; a = B.a.x - A.a.x; b = B.a.y - A.a.y; c = B.r; d =

6、sqr(c) - sqr(k) - sqr(a) - sqr(b); aa = 4 * sqr(a) + 4 * sqr(b); bb = 4 * b * d; cc = sqr(d) - 4 * sqr(a) * sqr(k); drt = sqr(bb) - 4 * aa * cc; if (drt 0) return 5; drt = sqrt (drt); ia.y = (-bb + drt) / 2 / aa; ib.y = (-bb - drt) / 2 / aa; if (abs (a) eps) ia.x = sqrt (sqr (k) - sqr (ia.y); ib.x =

7、 -ia.x; else ia.x = (2 * b * ia.y + d) / -2 / a; ib.x = (2 * b * ib.y + d) / -2 / a; ia.x += A.a.x; ia.y += A.a.y; ib.x += A.a.x; ib.y += A.a.y; if (abs (ia.y - ib.y) eps) if (abs (A.r + B.r - dd) eps) return 2; if (abs (dd - (max (A.r, B.r) - min (A.r, B.r) eps) return 3; return 4;/ 点到直线的距离double d

8、isptoline( point p, point l1, point l2) return fabs(xmult( p, l1, l2)/dist( l1, l2);/圆与直线的交点void intersection_line_circle( point c, double r, point l1, point l2 , point &p1, point &p2) point p = c; double t; p.x += l1.y - l2.y; p.y += l2.x - l1.x; p = intersection(p , c, l1, l2); t = sqrt( r*r - dis

9、t(p,c)*dist(p,c)/dist(l1,l2); p1.x = p.x + (l2.x - l1.x)*t; p1.y = p.y + (l2.y - l1.y)*t; p2.x = p.x - (l2.x - l1.x)*t; p2.y = p.y - (l2.y - l1.y)*t;void swap( double &x1, double &y1) double x = x1; x1 = y1; y1 = x;double dijkstra(int st, int en , int m) int i, j, k , l; int vismaxn; memset( vis, 0

10、,sizeof vis); for( i = 0; i m; i +) disi = fsti; disst = 0; visst = 1; for( i = 1; i m; i + ) int pos = -1; double min_len = inf; for( j = 1; j m; j + ) if( visj ) continue; if( disj min_len ) min_len = disj; pos = j; if( pos = -1) break; vispos = 1; for( j = 1; j dispos + fposj + eps) disj = dispos

11、 + fposj; return disen;int main() int t, i, j , n; int TT = 0; scanf(%d,&t); while( t - ) scanf(%d,&n); for( i = 0; i n; i + ) Ci.a.in(); scanf(%lf,&Ci.r); point star, end; star = C0.a; end = Cn-1.a; int cnt = 0; for( i = 0; i n; i + ) /去重 去包围 int flag = 1; for( j = 0; j 0) flag = 0; break; if(flag)

12、 Ccnt+ = Ci; n = cnt; /留下的圆的个数 cnt = 0; for( i = 0; i n; i + ) for( j = i + 1; j 0) continue; point u ,v; circle_intersect( Ci, Cj, u , v); pcnt+ = u; pcnt+ = v; int m = 0; / 这个图中点的个数 for( i = 0; i cnt; i + ) int flag =1; for( j = i + 1; j cnt; j + ) if(pi = pj) flag = 0 ; break; if( flag ) pm+ = pi

13、; int st = -1, en = -1; for( i = 0; i = 0; i- ) p i + 1 = pi; p0 = star; m + ; st = 0; if( en = -1 ) pm+ = end; en = m - 1; if( st = en | star = end ) printf(Case %d: ,+TT); printf(0.0000n); continue; /* printf( 点的信息 * %d n,m); for( i = 0 ; i m; i + ) printf( %d %lf %lf n, i, pi.x, pi.y ); printf( 圆

14、的信息: %d n,n ); for( i = 0; i n; i + ) printf( %lf %lf %lf n, Ci.a.x,Ci.a.y, Ci.r); */ for( i = 0; i m; i + ) for( j = i + 1; j m; j +) int c = 0; point u,v; for( int l= 0; l 0 ) continue; intersection_line_circle( Cl.a , Cl.r, pi, pj, u, v ); Tc.x1 = u.x; Tc+.x2 = v.x; int num = 0; double xx = min(

15、pi.x ,pj.x ), yy = max( pi.x, pj.x ); for( int l = 0 ; l 0 ) swap( Tl.x1, Tl.x2 ); if( sign( Tl.x2 - xx) = 0 ) continue; Tnum+ = Tl; c = num; sort( T, T + c, cmp); double max_hi = T0.x2; for( int l = 1; l c; l + ) if( sign( Tl.x1 - max_hi ) = 0) max_hi = max( max_hi , Tl.x2 ); else break; if( sign(

16、T0.x1 - xx) = 0) fij = fji = dist( pi , pj ); else fij = fji = inf; /* printf( 边长的信息： %d n, m ); for( i = 0; i m; i + ) for( j = 0; j = 0) printf(No such path.n); else printf(%.4lfn,ans); return 0;#include #include #include #include #include #include #include using namespace std;#define pi acos(-1.0

17、)#define eps 1e-8#define maxn 105int sign(double x) if( x eps;struct point double x,y; point() point(double x,double y):x(x),y(y) void in() scanf(%lf %lf,&x,&y); point operator -(const point &b)const return point( x - b.x , y - b.y); point operator +(const point &b)const return point( x + b.x, y + b

18、.y ); bool operator =(const point &b)const return sign( x - b.x) = 0 & sign( y - b.y) = 0; ;point pmaxn;point sun,er;double t1,t2,t,r;double xmult( point a, point b, point o ) return ( a.x - o.x )*( b.y - o.y ) - ( a.y - o.y )*( b.x - o.x );/ 求两条直线的交点point intersection(point u1, point u2, point v1,

19、point v2) point ret = u1; double t = (u1.x - v1.x)*(v1.y - v2.y) - ( u1.y - v1.y)*(v1.x - v2.x) /(u1.x - u2.x)*(v1.y - v2.y) - (u1.y - u2.y)*(v1.x - v2.x); ret.x += ( u2.x - u1.x)*t; ret.y += ( u2.y - u1.y)*t; return ret;/求三角形重心point barycenter(point a, point b, point c) point u1, u2, v1, v2; u1.x =

20、 ( a.x + b.x)/2; u1.y = ( a.y + b.y)/2; u2 = c; v1.x = ( a.x + c.x)/2; v1.y = ( a.y + c.y)/2; v2 = b; return intersection( u1, u2, v1, v2);/求多边形重心(顺时针、逆时针都可以)point barycenter(int n, point *P)/求重心 point ret , t; double t1 = 0, t2; int i; ret.x = ret.y = 0; for( i = 1; i eps) t = barycenter(p0, pi, pi

21、+1); ret.x += t.x*t2; ret.y += t.y*t2; t1 += t2; if(fabs(t1) eps) ret.x /= t1, ret.y /= t1; return ret;double dist( point a, point b) double x = a.x - b.x; double y = a.y - b.y; return sqrt( x*x + y*y);point rotate( point a,double ang ) /将向量 旋转角度(逆时针) point res; res.x = a.x*cos(ang) - a.y*sin(ang);

22、res.y = a.x*sin(ang) + a.y*cos(ang); return res;bool cmp1( point a, point b) if( sign( a.y - b.y) 0 ) return true; else if( sign( a.x - b.x) 0 ) return true; return false;double disptoline( point p, point l1, point l2) / 点到直线的距离 return fabs(xmult( p, l1, l2)/dist( l1, l2);point intersection_line_cir

23、cle( point c, double r, point l1, point l2)/圆与直线的交点 point p = c; double t; p.x += l1.y - l2.y; p.y += l2.x - l1.x; p = intersection(p , c, l1, l2); t = sqrt( r*r - dist(p,c)*dist(p,c)/dist(l1,l2); point p1,p2; p1.x = p.x + (l2.x - l1.x)*t; p1.y = p.y + (l2.y - l1.y)*t; p2.x = p.x - (l2.x - l1.x)*t;

24、p2.y = p.y - (l2.y - l1.y)*t; /两个交点取一个更近的 if( sign(dist( p1, sun) - dist(p2, sun) = 0) return p2; return p1;void dot_line_cirlce( point p, point o, double r, point &p1, point &p2)/点p在圆上的两个切点 double len = dist( p, o ) , ce = sqrt( len*len - r*r); double ang = acos(ce/len); point u = o - p; u.x = u.x

25、* ce/len; u.y = u.y * ce/len; p1 = rotate( u , ang ); p1 = p + p1; p2 = rotate( u , -ang ); p2 = p2 + p; return ;/ 判断u在线段l1 l2 之内bool same_line_side(point u, point l1, point l2) if( sign( (l1.x - u.x)*( l2.x - u.x) = 0 & sign( (l1.y - u.y)*( l2.y - u.y) = 0 ) return true; return false;int main() int i, n, j; while(scanf(%lf%lf,&sun.x,&sun.y)!=EOF) er.in(); scanf(%lf,&r); scanf(%d%lf%lf%lf,&n,&t1,&t2,&t); / 公转 自转 for( i = 0; i n ; i + ) pi.in(); point cen = ba