专栏首页小L的魔法馆HDU 6354--Everything Has Changed(判断两圆关系+弧长计算)

HDU 6354--Everything Has Changed(判断两圆关系+弧长计算)

  • 题目
  • 题意:首先给定一个以原点为圆心,R为半径的圆,之后在给m个圆,这些圆可能会和原来的圆有所交集,计算开始的圆剩余区域的周长,不包括内部周长。
  • 首先判定两圆关系,如果内含,直接加上圆的周长,如果相交,在计算对应弧长,其他情况都不用计算。在计算圆心角的时候,有个精度问题,只用本身半径算出来的弧度会不够,所有用上两个圆的半径。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const double PI = acos(-1.0);
typedef struct point {
    double x;
    double y;
    point() {

    }
    point(double a, double b) {
        x = a;
        y = b;
    }
    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.y);
    }
    //数乘计算
    point operator *(const double &k)const {    //返回相乘后的新点
        return point(x * k, y * k);
    }
    point operator /(const double &k)const {    //返回相除后的新点
        return point(x / k, y / k);
    }
    double operator ^(const point &b)const {    //叉乘
        return x*b.y - y*b.x;
    }
    double operator *(const point &b)const {    //点乘
        return x*b.x + y*b.y;
    }
    double len() {      //返回直角三角形的斜边长
        return hypot(x, y);
    }
}point;
typedef struct circle {//圆
    double r;
    point centre;
    circle() {

    }
    circle(point a,double b) {
        centre = a;
        r = b;
    }
    double len() {
        return 2 * PI*r;
    }
    double area() {
        return PI*r*r;
    }
}circle;
circle  org;
double ans, r;
int t, m;
double dist(point p1, point p2) {       //返回平面上两点距离
    return sqrt((p1 - p2)*(p1 - p2));
}
int CircleInterNum(circle a, circle b) {
    double fh = fabs(a.r + b.r), fc = fabs(a.r - b.r), d = dist(a.centre, b.centre);
    if (d>fh)
        return -2;  //外离,没有交点
    if (d==fh)
        return -1;  //外切,一个交点
    if (d > fc&&d < fh)
        return 0;   //相交,两个交点
    if (d == fc)
        return 1;   //内切,一个交点
    if (d < fc&&d>=0)
        return 2;   //内含,没有交点
}

void CircleIntteLen(circle a, circle b) {
    double d = dist(a.centre, b.centre);
    double t = (d*d + a.r*a.r - b.r*b.r) / (2.0 * d);
    double h = sqrt((a.r*a.r) - (t*t))*2;
    double angle_a = 2*acos((a.r*a.r +d*d-b.r*b.r) / (2.0 * a.r*d));    //余弦公式计算圆心角,反三角计算出的是弧度
    double angle_b = 2*acos((b.r*b.r +d*d-a.r*a.r) / (2.0 * b.r*d));
    double la = angle_a*a.r;
    double lb = angle_b*b.r;
    ans += (lb-la);
}
int main(void) {
    cin >> t;
    while (t-- > 0) {
        org.centre = point(0, 0);
        cin >> m >> r;
        org.r = r;
        ans = org.len();
        double x, y, rt;
        for (int i = 0; i < m; i++) {
            cin >> x >> y >> rt;
            circle tmp = circle(point(x, y), rt);
            if (CircleInterNum(org, tmp) == 0)
                CircleIntteLen(org, tmp);
            if (CircleInterNum(org, tmp) == 1)
                ans += tmp.len();
        }
        printf("%.15f\n",ans);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Codeforces Good Bye 2018 D (1091D)

    题目:New Year and the Permutation Concatenation

    ACM算法日常
  • EM Algorithm

    EM算法和之前学的都不太一样,EM算法更多的是一种思想,所以后面用几个例子讲解,同时也会重点讲解GMM高斯混合模型。

    西红柿炒鸡蛋
  • 网易云音乐为什么这么懂你?

    相信大家这几天的朋友圈已经被网易云音乐的年度听歌报告给刷屏了吧!不知道你们2018的年度关键词是什么,我的关键词是“青春”。

    谭庆波
  • 鸿篇巨制 —— LevelDB 的整体架构

    本节信息量很大,我们要从整体上把握 LevelDB 这座大厦的结构。当我们熟悉了整体的结构,接下来就可以各个击破来细致了解它的各种微妙的细节了。

    老钱
  • 创业者注意了!大数据教你如何在众筹网站上成功融资

    有好点子,想创业,但没钱,怎么办?Kickstarter是美国著名的众筹网站,在这里可以帮有好点子的创业者实现梦想!本文数据侠抓取了Kickstarter的众筹...

    DT数据侠
  • BAT 经典算法笔试题 —— 逆转单向链表

    不善言谈的优秀程序员在面试中往往是要吃巨亏的,你没有办法通过说话来轻易证明自己的实力。不论是大厂还是小厂,大部分面试官都不具备优秀的面试能力,它们也只能通过三言...

    老钱
  • 数学原来这么有趣,66组超炫动图唤醒你的思维!

    无论怎样,看完这一组动图,你不仅能够感受到数学美丽的一面,同时也会对我们常见的公式定理有更深刻、直观的理解!

    华章科技
  • 【CVPR2018最佳论文提名】Deep Learning of Graph Matching论文解读

    作为一种常用的图数据处理技术,图匹配在计算机视觉中拥有丰富的应用场景和研究价值。CVPR2018最佳论文提名的工作Deep Learning of Graph ...

    SIGAI学习与实践平台
  • BAT 经典算法笔试题: 镜像二叉树

    再过不到 2 个月,互联网行业就要再次迎来面试高峰了。为了让大家能顺利通过所有面试环节必经的笔试阶段,我提前给大伙准备了一套常见的算法笔试题。这套算法题来源于 ...

    老钱
  • 来聊一聊 Spring 框架的前生今世

    这里的 Pivotal 团队肯定就是 Spring Boot 的研发团队了,那么这个 Pivotal 团队到底是个什么来头呢?和 Spring 又有那些关系?不...

    美码师

扫码关注云+社区

领取腾讯云代金券