首页 > 代码库 > SPOJ CIRU The area of the union of circles (计算几何)
SPOJ CIRU The area of the union of circles (计算几何)
题意:求 m 个圆的并的面积。
析:就是一个板子题,还有要注意圆的半径为0的情况。
代码如下:
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <string> #include <cstdlib> #include <cmath> #include <iostream> #include <cstring> #include <set> #include <queue> #include <algorithm> #include <vector> #include <map> #include <cctype> #include <cmath> #include <stack> #include <sstream> #define debug() puts("++++"); #define gcd(a, b) __gcd(a, b) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define freopenr freopen("in.txt", "r", stdin) #define freopenw freopen("out.txt", "w", stdout) using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<double, int> P; const int INF = 0x3f3f3f3f; const double inf = 0x3f3f3f3f3f3f; const double PI = acos(-1.0); const double eps = 1e-8; const int maxn = 1e4 + 10; const int mod = 1e6; const int dr[] = {-1, 0, 1, 0}; const int dc[] = {0, 1, 0, -1}; const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"}; int n, m; const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; inline bool is_in(int r, int c){ return r >= 0 && r < n && c >= 0 && c < m; } int dcmp(double x){ if(fabs(x) < eps) return 0; if(x > 0) return 1; return -1; } double sqr(double x){ return x * x; } struct Point{ double x, y; Point(){ } Point(double a, double b) : x(a), y(b) { } void input(){ scanf("%lf %lf", &x, &y); } friend Point operator + (const Point &a, const Point &b){ return Point(a.x + b.x, a.y + b.y); } friend Point operator - (const Point &a, const Point &b){ return Point(a.x - b.x, a.y - b.y); } friend bool operator == (const Point &a, const Point &b){ return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; } friend Point operator * (const Point &a, const double &b){ return Point(a.x * b, a.y * b); } friend Point operator * (const double &b, const Point &a){ return Point(a.x * b, a.y * b); } friend Point operator / (const Point &a, const double &b){ return Point(a.x / b, a.y / b); } double norm(){ return sqrt(sqr(x) + sqr(y)); } }; double cross(const Point &a, const Point &b){ return a.x * b.y - a.y * b.x; } struct Circle{ Point p; double r; bool operator < (const Circle &o) const{ if(dcmp(r-o.r) != 0) return dcmp(r-o.r) == -1; if(dcmp(p.x-o.p.x) != 0) return dcmp(p.x - o.p.x) == -1; return dcmp(p.y - o.p.y) == -1; } bool operator == (const Circle &o) const{ return dcmp(r - o.r) == 0 && dcmp(p.x - o.p.x) == 0 && dcmp(p.y - o.p.y) == 0; } }; Point rotate(const Point &p, double cost, double sint){ double x = p.x, y = p.y; return Point(x*cost - y*sint, x*sint + y*cost); } pair<Point, Point> crossPoint(Point ap, double ar, Point bp, double br){ double d = (ap - bp).norm(); double cost = (ar*ar + d*d - br*br) / (2.0*ar*d); double sint = sqrt(1.0 - cost*cost); Point v = (bp - ap) / (bp - ap).norm() * ar; return make_pair(ap+rotate(v, cost, -sint), ap+rotate(v, cost, sint)); } pair<Point, Point> crossPoint(const Circle &a, const Circle &b){ return crossPoint(a.p, a.r, b.p, b.r); } Circle c[maxn], tc[maxn]; #include<complex> struct Node{ Point p; double a; int d; Node(const Point &pp, double aa, int dd) : p(pp), a(aa), d(dd) { } bool operator < (const Node &o) const{ return a < o.a; } }; double arg(Point p){ return arg(complex<double> (p.x, p.y)); } double solve(){ sort(tc, tc + m); m = unique(tc, tc + m) - tc; n = 0; for(int i = m-1; i >= 0; --i){ bool ok = true; for(int j = i+1; j < m; ++j){ double d = (tc[i].p - tc[j].p).norm(); if(dcmp(d - abs(tc[i].r - tc[j].r)) <= 0){ ok = false; break; } } if(ok) c[n++] = tc[i]; } double ans = 0.0; for(int i = 0; i < n; ++i){ vector<Node> event; Point boundary = c[i].p + Point(-c[i].r, 0); event.push_back(Node(boundary, -PI, 0)); event.push_back(Node(boundary, PI, 0)); for(int j = 0; j < n; ++j){ if(i == j) continue; double d = (c[i].p - c[j].p).norm(); if(dcmp(d - (c[i].r + c[j].r)) < 0){ pair<Point, Point> ret = crossPoint(c[i], c[j]); double x = arg(ret.first - c[i].p); double y = arg(ret.second - c[i].p); if(dcmp(x - y) > 0){ event.push_back(Node(ret.first, x, 1)); event.push_back(Node(boundary, PI, -1)); event.push_back(Node(boundary, -PI, 1)); event.push_back(Node(ret.second, y, -1)); } else{ event.push_back(Node(ret.first, x, 1)); event.push_back(Node(ret.second, y, -1)); } } } sort(event.begin(), event.end()); int sum = event[0].d; for(int j = 1; j < event.size(); ++j){ if(sum == 0){ ans += cross(event[j-1].p, event[j].p) / 2.0; double x = event[j-1].a; double y = event[j].a; double area = c[i].r * c[i].r * (y-x) / 2.0; Point v1 = event[j-1].p - c[i].p; Point v2 = event[j].p - c[i].p; area -= cross(v1, v2) / 2.0; ans += area; } sum += event[j].d; } } return ans; } int main(){ while(scanf("%d", &n) == 1){ m = 0; for(int i = 0; i < n; ++i){ tc[m].p.input(); scanf("%lf", &tc[m].r); if(dcmp(tc[m].r) <= 0) continue; ++m; } printf("%.3f\n", solve()); } return 0; }
SPOJ CIRU The area of the union of circles (计算几何)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。