1.三角形的所有端点

2.过所有三角形的端点对所有圆做切线,得到所有切点。

3.做任意两圆的外公切线,得到所有切点。

对上述所有点求凸包,标记每个点是三角形上的点还是某个圆上的点。

求完凸包后,因为所有点都是按逆时针(或顺时针)排好序的,如果相邻两点在同一圆上,那么求这段圆弧的距离,否则求这段直线的距离。最后得到所有周长。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm> using namespace std; const double eps = 1e-;
const double PI = acos(-1.0);
const int MAXN = ; struct Point
{
double x, y;
int id; //点标号,标记是否在同一个圆上
Point() { }
Point( double x, double y ):x(x), y(y) { }
Point( double x, double y, int id ):x(x), y(y), id(id) { }
void readPoint()
{
scanf( "%lf%lf", &x, &y );
return;
}
}; struct Circle
{
Point c; //圆心坐标
double r; //半径
Circle() {}
Circle( Point c, double r ): c(c), r(r) {}
Point getPoint( double theta ) //根据极角返回圆上一点的坐标
{
return Point( c.x + cos(theta)*r, c.y + sin(theta)*r );
}
void readCircle()
{
scanf("%lf%lf%lf", &c.x, &c.y, &r );
return;
}
}; typedef Point Vector; Vector operator+( Vector A, Vector B ) //向量加
{
return Vector( A.x + B.x, A.y + B.y );
} Vector operator-( Vector A, Vector B ) //向量减
{
return Vector( A.x - B.x, A.y - B.y );
} Vector operator*( Vector A, double p ) //向量数乘
{
return Vector( A.x * p, A.y * p );
} Vector operator/( Vector A, double p ) //向量数除
{
return Vector( A.x / p, A.y / p );
} int dcmp( double x ) //控制精度
{
if ( fabs(x) < eps ) return ;
else return x < ? - : ;
} bool operator<( const Point& A, const Point& B ) //两点比较
{
return dcmp( A.x - B.x) < || ( dcmp(A.x - B.x ) == && dcmp( A.y - B.y ) < );
} bool operator>( const Point& A, const Point& B ) //两点比较
{
return dcmp( A.x - B.x) > || ( dcmp(A.x - B.x ) == && dcmp( A.y - B.y ) > );
} bool operator==( const Point& a, const Point& b ) //两点相等
{
return dcmp( a.x - b.x ) == && dcmp( a.y - b.y ) == ;
} double Cross( Vector A, Vector B ) //向量叉积
{
return A.x * B.y - A.y * B.x;
} double PointDis( Point a, Point b ) //两点距离的平方
{
return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
} //求凸包,graham算法,O(nlogn),返回凸包点的个数
int graham( Point *p, int n, Point *ch )
{
if ( n <= ) return ;
int top = ;
sort( p, p + n ); ch[ top ] = p[];
ch[ ++top ] = p[];
ch[ ++top ] = p[]; top = ; for ( int i = ; i < n; ++i )
{
while ( top && dcmp( Cross( ch[top] - ch[top - ], p[i] - ch[top - ] ) ) <= ) --top;
ch[++top] = p[i];
}
int len = top;
ch[++top] = p[n - ];
for ( int i = n - ; i >= ; --i )
{
while ( top > len && dcmp( Cross( ch[top] - ch[top - ], p[i] - ch[top - ] ) ) <= ) --top;
ch[++top] = p[i];
}
return top;
} //过定点做圆的切线,得到切点,返回切点个数
//tps保存切点坐标
int getTangentPoints( Point p, Circle C, Point *tps )
{
int cnt = ; double dis = sqrt( PointDis( p, C.c ) );
int aa = dcmp( dis - C.r );
if ( aa < ) return ; //点在圆内
else if ( aa == ) //点在圆上,该点就是切点
{
tps[cnt] = p;
++cnt;
return cnt;
} //点在圆外,有两个切点
double base = atan2( p.y - C.c.y, p.x - C.c.x );
double ang = acos( C.r / dis );
//printf( "base = %f ang=%f\n", base, ang );
//printf( "base-ang=%f base+ang=%f \n", base - ang, base + ang ); tps[cnt] = C.getPoint( base - ang ), ++cnt;
tps[cnt] = C.getPoint( base + ang ), ++cnt; return cnt;
} //求两圆外公切线切点,返回切线个数
//p是圆c2在圆c1上的切点
int makeCircle( Circle c1, Circle c2, Point *p )
{
int cnt = ;
double d = sqrt( PointDis(c1.c, c2.c) ), dr = c1.r - c2.r;
double b = acos(dr / d);
double a = atan2( c2.c.y - c1.c.y, c2.c.x - c1.c.x );
double a1 = a - b, a2 = a + b;
p[cnt++] = Point(cos(a1) * c1.r, sin(a1) * c1.r) + c1.c;
p[cnt++] = Point(cos(a2) * c1.r, sin(a2) * c1.r) + c1.c;
return cnt;
} double DisOnCircle( Point a, Point b, Circle c ) //求圆上一段弧长
{
Point o = c.c;
double A = sqrt( PointDis( o, a ) );
double B = sqrt( PointDis( o, b ) );
double C = sqrt( PointDis( a, b ) );
double alpha = acos( ( A*A + B*B - C*C ) / ( 2.0*A*B ) );
if ( dcmp( Cross( o-a, o-b ) ) < ) return alpha * c.r;
else return ( 2.0*PI - alpha ) * c.r;
} /**********************以上模板**********************/ int cntC, cntT; //圆的个数,三角形的个数
Circle yuan[MAXN]; //所有圆
Point PP[]; //所有点
Point tubao[]; //凸包
int totPP; //点总数 void showP( Point *p, int nn )
{
printf( "allP = %d\n", nn );
for ( int i = ; i < nn; ++i )
printf("%f %f\n", p[i].x, p[i].y );
puts("-------------------------");
return;
} int main()
{
//freopen( "10022.in", "r", stdin );
//freopen( "s.out", "w", stdout );
while ( scanf( "%d%d", &cntC, &cntT ) == )
{
totPP = ;
for ( int i = ; i < cntC; ++i )
yuan[i].readCircle();
for ( int i = ; i < cntT; ++i )
{
for ( int j = ; j < ; ++j )
{
PP[totPP].readPoint();
PP[totPP].id = -(totPP+);
++totPP;
}
} if ( cntC == && cntT == )
{
printf("%.6f\n", 2.0 * PI * yuan[].r );
continue;
} int pretot = totPP;
//求两圆的外切点
for ( int i = ; i < cntC; ++i )
for ( int j = i + ; j < cntC; ++j )
{
Point PonA[], PonB[];
makeCircle( yuan[i], yuan[j], PonA );
int ans = makeCircle( yuan[j], yuan[i], PonB );
for ( int k = ; k < ans; ++k )
{
PonA[k].id = i;
PonB[k].id = j;
PP[totPP++] = PonA[k];
PP[totPP++] = PonB[k];
}
} //求所有点与所有圆的切点
for ( int i = ; i < pretot; ++i )
{
for ( int j = ; j < cntC; ++j )
{
Point qiedian[];
int ans = getTangentPoints( PP[i], yuan[j], qiedian );
for ( int k = ; k < ans; ++k )
{
qiedian[k].id = j;
PP[totPP++] = qiedian[k];
}
}
} //showP( PP, totPP );
int cntBao = graham( PP, totPP, tubao );
//puts("*********");
//showP( tubao, cntBao );
double girth = 0.0;
tubao[cntBao] = tubao[]; for ( int i = ; i <= cntBao; ++i )
{
if ( tubao[i].id == tubao[i - ].id ) //如果两点在同一个圆上
girth += DisOnCircle( tubao[i], tubao[i - ], yuan[ tubao[i].id ] );
else
girth += sqrt( PointDis( tubao[i], tubao[i - ] ) ); } printf( "%.5lf\n", girth );
}
return ;
}

最新文章

  1. 使用面向 iOS 的本机插件扩展 PhoneGap
  2. 【NOIP2009 T3】 最佳贸易 (双向SPFA)
  3. MySQL入门手册
  4. 菜鸟教程之工具使用(十一)——Eclipse去掉未使用的引用
  5. livereload的简单使用
  6. leetcode 37 Sudoku Solver java
  7. Echarts事件
  8. 【总算解决了】A network-related or instance-specific error occurred while establishing a connection to SQL Server
  9. 用JAVA写一个冒泡排序
  10. CODEVS3269混合背包+二进制优化
  11. 应用shell脚本停启Tomcat
  12. Ch02 课堂作业
  13. Mybatis 配置resultMap一对多关联映射
  14. MySQL导入SQL语句报错 : MySQL server has gone away (已解决)
  15. 网络编程之Socket异步编程
  16. 解题(JuZhengCalculate-矩阵乘法计算量)
  17. Android--自定义半圆环型进度(带动画)
  18. Linux-使用 yum 升级 gcc 到 4.8
  19. [COGS2426][HZOI 2016]几何
  20. laravel 框架给数组分页

热门文章

  1. 第一个AngularJS指令
  2. currency 过滤器
  3. Filter,一种aop编程思想的体现
  4. Java日志框架介绍
  5. BZOJ1491: [NOI2007]社交网络(Floyd 最短路计数)
  6. Ubuntu安装MySQL及使用Xshell连接MySQL出现的问题(2003-Can&#39;t connect to MySql server及1045错误)
  7. 前端之HTML和CSS
  8. VM虚拟机里的Ubuntu系统怎么设置屏幕分辨率
  9. float元素浮动后高度不一致导致错位的解决办方法
  10. MySQL的隐式类型转换整理总结