- 浏览: 738668 次
文章分类
最新评论
-
dfjjfxyl:
开源项目推荐网站:http://binlily.imwork. ...
JAVA开源项目 -
喵喵大神:
这类免费API还是挺多的,博客上也整理过:https://my ...
Web Api --智能Api接口
Hdu 4667 Building Fence
这个题有两种解法:
方法一:将圆均分2000个点,暴力水过
程序简单,好写
精度要求比较高,无从下手的时候可以尝试一下,一旦精度要求比较高不过的可能性比较大...
交c++超时,g++800+ms,表示不理解
#include <cstdio> #include <ctime> #include <cstdlib> #include <cstring> #include <queue> #include <string> #include <set> #include <stack> #include <map> #include <cmath> #include <vector> #include <iostream> #include <algorithm> #include <bitset> #include <fstream> using namespace std; //LOOP #define FF(i, a, b) for(int i = (a); i < (b); ++i) #define FE(i, a, b) for(int i = (a); i <= (b); ++i) #define FED(i, b, a) for(int i = (b); i>= (a); --i) #define REP(i, N) for(int i = 0; i < (N); ++i) #define CLR(A,value) memset(A,value,sizeof(A)) #define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++) //OTHER #define SZ(V) (int)V.size() #define PB push_back #define MP make_pair #define all(x) (x).begin(),(x).end() #define EQ(a, b) (fabs((a) - (b)) <= 1e-10) //INPUT #define RI(n) scanf("%d", &n) #define RII(n, m) scanf("%d%d", &n, &m) #define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k) #define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p) #define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q) #define RS(s) scanf("%s", s) //OUTPUT #define WI(n) printf("%d\n", n) #define WS(n) printf("%s\n", n) //debug //#define online_judge #define enter #ifndef online_judge #define debugt(a) cout << (#a) << "=" << a << " "; #define debugI(a) debugt(a) cout << endl #define debugII(a, b) debugt(a) debugt(b) cout << endl #define debugIII(a, b, c) debugt(a) debugt(b) debugt(c) cout << endl #define debugIV(a, b, c, d) debugt(a) debugt(b) debugt(c) debugt(d) cout << endl #else #define debugI(v) #define debugII(a, b) #define debugIII(a, b, c) #endif typedef long long LL; typedef unsigned long long ULL; typedef vector <int> VI; const int INF = 1000000000; const double eps = 1e-10; const int MOD = 100000007; const int MAXN = 10000000; const double PI = acos(-1.0); ///*************基础***********/ inline int dcmp(double x) { if(fabs(x) < eps) return 0; else return x < 0 ? -1 : 1; } struct Point { double x, y; Point(double x=0, double y=0):x(x),y(y) { } inline void read() { scanf("%lf%lf", &x, &y); } }; typedef vector<Point> Polygon; typedef Point Vector; inline Vector operator + (Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); } inline Vector operator - (Point A, Point B) { return Vector(A.x-B.x, A.y-B.y); } inline Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); } inline Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); } inline bool operator < (const Point& a, const Point& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); } inline bool operator == (const Point& a, const Point &b) { return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0; } inline double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; } inline double Length(Vector A) { return sqrt(Dot(A, A)); } inline double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); } inline double angle(Vector v) { return atan2(v.y, v.x); } inline double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; } inline Vector vecunit(Vector x) { return x / Length(x); //单位向量 } inline Vector Normal(Vector x) { return Point(-x.y, x.x) / Length(x); //垂直法向量 } inline Vector Rotate(Vector A, double rad) { return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad)); } // 点集凸包 // 如果不希望在凸包的边上有输入点,把两个 <= 改成 < // 注意:输入点集会被修改 vector<Point> ConvexHull(vector<Point>& p) { // 预处理,删除重复点 sort(p.begin(), p.end()); p.erase(unique(p.begin(), p.end()), p.end()); int n = p.size(); int m = 0; vector<Point> ch(n+1); for(int i = 0; i < n; i++) { while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--; ch[m++] = p[i]; } int k = m; for(int i = n-2; i >= 0; i--) { while(m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--; ch[m++] = p[i]; } if(n > 1) m--; ch.resize(m); return ch; } inline double dist(Point a, Point b) { return Length(a - b); } /************圆************/ struct Circle { Point c; double r; Circle() {} Circle(Point c, double r):c(c), r(r) {} inline Point point(double a) //根据圆心角求点坐标 { return Point(c.x+cos(a)*r, c.y+sin(a)*r); } }; vector<Point> p, ans; const double interval = PI / 1000; int main() { // freopen("0.txt", "r", stdin); int N, M, size; Point input; double r, tx, ty, dis, ang; while (~RII(N, M)) { ans.clear(), p.clear(); dis = 0; REP(i, N) { scanf("%lf%lf%lf", &tx, &ty, &r); for (double ang = 0; ang < 2 * PI; ang += interval) { input.x = tx + cos(ang) * r; input.y = ty + sin(ang) * r; p.push_back(input); } } REP(i, M) { input.read(); p.push_back(input); input.read(); p.push_back(input); input.read(); p.push_back(input); } ans = ConvexHull(p); size = ans.size(); REP(i, size - 1) { dis += Length(ans[i] - ans[i + 1]); } dis += dist(ans[size - 1], ans[0]); printf("%.5lf\n", dis); } return 0; }
方法二:
将有可能构成凸包的点计算出来,包括 三角形的顶点,三角形顶点与各个圆的切点,任意两个圆的切点
然后计算凸包即可
有两个要注意的地方,第一是求凸包边长时候,需要判断一下当前计算的两个点是否在同一个圆上,若是则需要计算圆弧长度
第二是只有一个圆的时候需要特判
#include <cstdio> #include <ctime> #include <cstdlib> #include <cstring> #include <queue> #include <string> #include <set> #include <stack> #include <map> #include <cmath> #include <vector> #include <iostream> #include <algorithm> #include <bitset> #include <fstream> using namespace std; //LOOP #define FF(i, a, b) for(int i = (a); i < (b); ++i) #define FE(i, a, b) for(int i = (a); i <= (b); ++i) #define FED(i, b, a) for(int i = (b); i>= (a); --i) #define REP(i, N) for(int i = 0; i < (N); ++i) #define CLR(A,value) memset(A,value,sizeof(A)) #define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++) //OTHER #define SZ(V) (int)V.size() #define PB push_back #define MP make_pair #define all(x) (x).begin(),(x).end() //INPUT #define RI(n) scanf("%d", &n) #define RII(n, m) scanf("%d%d", &n, &m) #define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k) #define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p) #define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q) #define RS(s) scanf("%s", s) //OUTPUT #define WI(n) printf("%d\n", n) #define WS(n) printf("%s\n", n) //debug //#define online_judge #ifndef online_judge #define debugt(a) cout << (#a) << "=" << a << " "; #define debugI(a) debugt(a) cout << endl #define debugII(a, b) debugt(a) debugt(b) cout << endl #define debugIII(a, b, c) debugt(a) debugt(b) debugt(c) cout << endl #define debugIV(a, b, c, d) debugt(a) debugt(b) debugt(c) debugt(d) cout << endl #else #define debugI(v) #define debugII(a, b) #define debugIII(a, b, c) #define debugIV(a, b, c, d) #endif typedef long long LL; typedef unsigned long long ULL; typedef vector <int> VI; const int INF = 0x3f3f3f3f; const double eps = 1e-10; const int MOD = 100000007; const int MAXN = 1000010; const double PI = acos(-1.0); ///*************基础***********/ double torad(double deg) { return deg / 180 * PI; } inline int dcmp(double x) { if(fabs(x) < eps) return 0; else return x < 0 ? -1 : 1; } struct Point { double x, y; Point(double x=0, double y=0):x(x),y(y) { } inline void read() { scanf("%lf%lf", &x, &y); } }; typedef vector<Point> Polygon; typedef Point Vector; inline Vector operator + (Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); } inline Vector operator - (Point A, Point B) { return Vector(A.x-B.x, A.y-B.y); } inline Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); } inline Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); } inline bool operator < (Point a, Point b) { return a.x < b.x || (a.x == b.x && a.y < b.y); } inline bool operator == (Point a, Point b) { return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0; } inline double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; } inline double Length(Vector A) { return sqrt(Dot(A, A)); } inline double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); } inline double angle(Vector v) { return atan2(v.y, v.x); } inline double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; } inline Vector Unit(Vector x) { return x / Length(x); //单位向量 } inline Vector Normal(Vector x) { return Point(-x.y, x.x) / Length(x); //垂直法向量 } inline Vector Rotate(Vector A, double rad) { return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad)); } inline double Area2(Point A, Point B, Point C) { return Cross(B-A, C-A); } template <class T> T sqr(T x) { return x * x ; } // 点集凸包 // 如果不希望在凸包的边上有输入点,把两个 <= 改成 < // 注意:输入点集会被修改 vector<Point> ConvexHull(vector<Point>& p) { // 预处理,删除重复点 sort(p.begin(), p.end()); p.erase(unique(p.begin(), p.end()), p.end()); int n = p.size(); int m = 0; vector<Point> ch(n+1); for(int i = 0; i < n; i++) { while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--; ch[m++] = p[i]; } int k = m; for(int i = n-2; i >= 0; i--) { while(m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--; ch[m++] = p[i]; } if(n > 1) m--; ch.resize(m); return ch; } inline double dist(Point a, Point b) { return Length(a - b); } /************圆************/ struct Circle { Point c; double r; Circle() {} Circle(Point c, double r):c(c), r(r) {} inline Point point(double a) //根据圆心角求点坐标 { return Point(c.x+cos(a)*r, c.y+sin(a)*r); } inline void read() { scanf("%lf%lf%lf", &c.x, &c.y, &r); } }; //求a点到b点(逆时针)在的圆上的圆弧长度 double DisOnCircle(Point a, Point b, Circle C) { double ang1 = angle(a - C.c); double ang2 = angle(b - C.c); if (ang2 < ang1) ang2 += 2 * PI; return C.r * (ang2 - ang1); } // 过点p到圆C的切点 int getTangentPoints(Point p, Circle C, vector<Point>& v) { Vector u = C.c - p; double dist = Length(u); if(dist < C.r) return 0; else if(dcmp(dist - C.r) == 0) // p在圆上,只有一条切线 { v.push_back(p); return 1; } else { double ang = asin(C.r / dist); double d = sqrt(dist * dist - C.r * C.r); v.push_back(p + Unit(Rotate(u, -ang)) * d); v.push_back(p + Unit(Rotate(u, +ang)) * d); return 2; } } //圆A与圆B的切点 void getTangentPoints(Circle A, Circle B, vector<Point>& a) { if (A.r < B.r) swap(A, B); ///**************************** int d2 = sqr(A.c.x - B.c.x) + sqr(A.c.y - B.c.y); int rdiff = A.r - B.r, rsum = A.r + B.r; if (d2 < rdiff * rdiff) return; //内含 ///*************************************** double base = atan2(B.c.y - A.c.y, B.c.x - A.c.x); if (d2 == 0 && A.r == B.r) return; //无线多条切线 if (d2 == rdiff * rdiff) //内切, 1条切线 { ///********************** a.push_back(A.point(base)); a.push_back(B.point(base)); return; } //有外公切线 double ang = acos((A.r - B.r) / sqrt(d2 * 1.0)); a.push_back(A.point(base + ang)); a.push_back(B.point(base + ang)); a.push_back(A.point(base - ang)); a.push_back(B.point(base - ang)); if (d2 == rsum * rsum) //一条内公切线 { a.push_back(A.point(base)); a.push_back(B.point(PI + base)); } else if (d2 > rsum * rsum) //两条内公切线 { double ang = acos((A.r + B.r) / sqrt(d2 * 1.0)); a.push_back(A.point(base + ang)); a.push_back(B.point(PI + base + ang)); a.push_back(A.point(base - ang)); a.push_back(B.point(PI + base - ang)); } } inline bool OnCircle(Point x, Circle c) { return dcmp(c.r - Length(c.c - x)) == 0; } Circle C[60]; Point P[160]; vector<Point> ch, sol; double t1, t2; int main() { int a, b; while (~RII(a, b)) { ch.clear(), sol.clear(); REP(i, a) C[i].read(); b *= 3; REP(i, b) { P[i].read(); sol.push_back(P[i]); } REP(i, b) REP(j, a) { getTangentPoints(P[i], C[j], sol); } FF(i, 0, a) FF(j, i + 1, a) { getTangentPoints(C[i], C[j], sol); } ch = ConvexHull(sol); double ans = 0; int len = ch.size(); REP(i, len) { REP(j, a) { if (OnCircle(ch[i], C[j]) && OnCircle(ch[(i + 1) % len], C[j])) { ans += DisOnCircle(ch[i], ch[(i + 1) % len], C[j]); goto end; } } ans += dist(ch[i], ch[(i + 1) % len]); end:; } if (a == 1 && b == 0) ans += 2 * PI * C[0].r; printf("%.5lf\n", ans); } return 0; }
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
HDU图论题目分类
Hdu 1237 解题代码