题解

题目描述

给定二维平面上两个三角形$\triangle ABC$$和$$\triangle DEF$。我们分别求出这两个三角形的外接圆（分别记为$O$、$P$，其中$O$、$P$分别是圆心，$R$、$r$分别是半径），计算两个外接圆的公共部分面积。

思路分析

1. 求外接圆的圆心与半径：

   对于任意三角形$\triangle ABC$，外接圆的圆心可以通过三角形三个顶点坐标求出。常用的方法为利用垂直平分线求交点。具体过程如下：

   • 设$A$、$B$、$C$的坐标分别为$(x_A, y_A)$、$(x_B, y_B)$、$(x_C, y_C)$。
   • 计算两边$AB$与$BC$的中垂线方程，解两直线交点得到圆心$O$。
   • 计算圆心$O$与任一点（例如$A$）的距离，即为半径$R$。

   同理求$\triangle DEF$的外接圆，设圆心为$P$，半径为$r$。

2. 计算两个圆的交集面积：

   已知两个圆中心分别为$O$与$P$，半径分别为$R$与$r$，它们之间的距离为$d$。根据$d$与$R$、$r$的大小关系分三种情况：

   • 无交点： 若$d\ge R + r$，则两个圆完全不相交，交集面积为$0$。

   • 包含关系： 若$d\le |R - r|$，则较小圆完全位于较大圆内部，交集面积即为较小圆的面积$\pi \cdot (\min(R,r))^2$。

   • 部分交叠： 否则，交集面积可以分为两部分计算：

     定义角$\theta$与$\phi$分别为：

     $\theta$=$2\arccos\left(\frac{d^2+R^2-r^2}{2dR}\right)$
     $\phi$=$2\arccos\left(\frac{d^2+r^2-R^2}{2dr}\right)$

     则交集面积$A$为：

     $A$=$\frac{R^2}{2}(\theta-\sin\theta)$+$\frac{r^2}{2}(\phi-\sin\phi)$

3. 总体流程：

   • 读入两个三角形的顶点坐标。
   • 对每个三角形通过计算几何中心与半径，求出外接圆。
   • 计算两个圆心距离$d$。
   • 根据$d$、$R$、$r$的关系判断情况，计算交集面积。

C++

#include <iostream>
#include <cmath>
using namespace std;

// 用于计算外接圆圆心和半径
struct Circle {
    double cx, cy, r;
};

// 根据三角形三个顶点计算外接圆
Circle circumcircle(double x1, double y1, double x2, double y2, double x3, double y3) {
    Circle circle;
    // 计算分母 D = 2*(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))
    double D = 2 * (x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2));
    // 注意：题目保证三角形存在，所以 D 不会为 0
    double x1s = x1*x1 + y1*y1;
    double x2s = x2*x2 + y2*y2;
    double x3s = x3*x3 + y3*y3;
    // 计算外接圆圆心坐标
    circle.cx = (x1s*(y2-y3) + x2s*(y3-y1) + x3s*(y1-y2)) / D;
    circle.cy = (x1s*(x3-x2) + x2s*(x1-x3) + x3s*(x2-x1)) / D;
    // 半径为圆心到任一顶点的距离
    circle.r = sqrt((circle.cx - x1) * (circle.cx - x1) + (circle.cy - y1) * (circle.cy - y1));
    return circle;
}

// 计算两个圆的公共面积
double circleIntersectionArea(const Circle &c1, const Circle &c2) {
    double d = sqrt((c1.cx - c2.cx) * (c1.cx - c2.cx) + (c1.cy - c2.cy) * (c1.cy - c2.cy));
    double R = c1.r, r = c2.r;
    // 如果两个圆没有交点
    if (d >= R + r) return 0.0;
    // 如果其中一个圆完全包含另一个圆
    if (d <= fabs(R - r)) {
        double minR = min(R, r);
        return 3.14159265358979323846 * minR * minR;
    }
    // 部分重叠情况
    double theta = 2 * acos((d*d + R*R - r*r) / (2*d*R));
    double phi = 2 * acos((d*d + r*r - R*R) / (2*d*r));
    double area1 = 0.5 * R*R * (theta - sin(theta));
    double area2 = 0.5 * r*r * (phi - sin(phi));
    return area1 + area2;
}

int main(){
    // 读入第一个三角形顶点坐标
    double xA, yA, xB, yB, xC, yC;
    cin >> xA >> yA >> xB >> yB >> xC >> yC;
    // 读入第二个三角形顶点坐标
    double xD, yD, xE, yE, xF, yF;
    cin >> xD >> yD >> xE >> yE >> xF >> yF;
    
    // 计算两个三角形的外接圆
    Circle circle1 = circumcircle(xA, yA, xB, yB, xC, yC);
    Circle circle2 = circumcircle(xD, yD, xE, yE, xF, yF);
    
    // 计算两个外接圆的公共面积
    double ans = circleIntersectionArea(circle1, circle2);
    
    // 保留足够精度输出
    cout.precision(10);
    cout << fixed << ans;
    
    return 0;
}

Python

import math

# 计算外接圆的函数，输入三角形三个顶点坐标
def circumcircle(x1, y1, x2, y2, x3, y3):
    # 计算分母 D = 2*(x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2))
    D = 2 * (x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2))
    # 计算各点平方和
    x1s = x1*x1 + y1*y1
    x2s = x2*x2 + y2*y2
    x3s = x3*x3 + y3*y3
    # 计算外接圆圆心的坐标
    cx = (x1s*(y2-y3) + x2s*(y3-y1) + x3s*(y1-y2)) / D
    cy = (x1s*(x3-x2) + x2s*(x1-x3) + x3s*(x2-x1)) / D
    # 半径为圆心到任意顶点的距离
    r = math.sqrt((cx - x1)**2 + (cy - y1)**2)
    return cx, cy, r

# 计算两个圆的交集面积
def circle_intersection_area(c1, c2):
    cx1, cy1, R = c1
    cx2, cy2, r = c2
    # 计算两个圆心之间的距离
    d = math.hypot(cx1 - cx2, cy1 - cy2)
    
    # 如果两个圆没有交点
    if d >= R + r:
        return 0.0
    # 如果其中一个圆完全包含在另一个圆内
    if d <= abs(R - r):
        minR = min(R, r)
        return math.pi * minR * minR
    # 部分重叠情况
    # 限制参数值在 [-1,1] 内
    term1 = (d*d + R*R - r*r) / (2*d*R)
    term1 = max(-1.0, min(1.0, term1))
    theta = 2 * math.acos(term1)
    term2 = (d*d + r*r - R*R) / (2*d*r)
    term2 = max(-1.0, min(1.0, term2))
    phi = 2 * math.acos(term2)
    area1 = 0.5 * R*R * (theta - math.sin(theta))
    area2 = 0.5 * r*r * (phi - math.sin(phi))
    return area1 + area2

def main():
    import sys
    data = sys.stdin.read().split()
    # 读取第一个三角形的坐标
    xA, yA, xB, yB, xC, yC = map(float, data[:6])
    # 读取第二个三角形的坐标
    xD, yD, xE, yE, xF, yF = map(float, data[6:12])
    
    # 求两个三角形外接圆
    circle1 = circumcircle(xA, yA, xB, yB, xC, yC)
    circle2 = circumcircle(xD, yD, xE, yE, xF, yF)
    
    # 计算交集面积
    ans = circle_intersection_area(circle1, circle2)
    # 保留足够精度输出
    print("{:.10f}".format(ans))
    
if __name__ == "__main__":
    main()

Java

import java.util.*;
import java.io.*;

public class Main {
    // 定义表示圆的类，保存圆心坐标和半径
    static class Circle {
        double cx, cy, r;
        Circle(double cx, double cy, double r) {
            this.cx = cx;
            this.cy = cy;
            this.r = r;
        }
    }

    // 根据三角形三个顶点坐标计算外接圆
    public static Circle circumcircle(double x1, double y1, double x2, double y2, double x3, double y3) {
        // 计算分母 D = 2*(x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2))
        double D = 2 * (x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2));
        double x1s = x1 * x1 + y1 * y1;
        double x2s = x2 * x2 + y2 * y2;
        double x3s = x3 * x3 + y3 * y3;
        // 计算圆心坐标
        double cx = (x1s*(y2-y3) + x2s*(y3-y1) + x3s*(y1-y2)) / D;
        double cy = (x1s*(x3-x2) + x2s*(x1-x3) + x3s*(x2-x1)) / D;
        // 半径为圆心与任意顶点的距离
        double r = Math.sqrt((cx - x1)*(cx - x1) + (cy - y1)*(cy - y1));
        return new Circle(cx, cy, r);
    }

    // 计算两个圆的交集面积
    public static double circleIntersectionArea(Circle c1, Circle c2) {
        double dx = c1.cx - c2.cx;
        double dy = c1.cy - c2.cy;
        double d = Math.hypot(dx, dy);
        double R = c1.r, r = c2.r;
        // 如果两个圆没有交点，则交集面积为0
        if(d >= R + r) return 0.0;
        // 如果其中一个圆完全包含另一个圆
        if(d <= Math.abs(R - r)){
            double minR = Math.min(R, r);
            return Math.PI * minR * minR;
        }
        // 部分重叠情况
        double term1 = (d*d + R*R - r*r) / (2 * d * R);
        term1 = Math.max(-1.0, Math.min(1.0, term1));
        double theta = 2 * Math.acos(term1);
        double term2 = (d*d + r*r - R*R) / (2 * d * r);
        term2 = Math.max(-1.0, Math.min(1.0, term2));
        double phi = 2 * Math.acos(term2);
        double area1 = 0.5 * R * R * (theta - Math.sin(theta));
        double area2 = 0.5 * r * r * (phi - Math.sin(phi));
        return area1 + area2;
    }

    public static void main(String[] args) throws Exception {
        // 输入使用Scanner
        Scanner sc = new Scanner(System.in);
        // 读取第一个三角形坐标
        double xA = sc.nextDouble(), yA = sc.nextDouble();
        double xB = sc.nextDouble(), yB = sc.nextDouble();
        double xC = sc.nextDouble(), yC = sc.nextDouble();
        // 读取第二个三角形坐标
        double xD = sc.nextDouble(), yD = sc.nextDouble();
        double xE = sc.nextDouble(), yE = sc.nextDouble();
        double xF = sc.nextDouble(), yF = sc.nextDouble();
        
        // 计算两个三角形对应外接圆
        Circle circle1 = circumcircle(xA, yA, xB, yB, xC, yC);
        Circle circle2 = circumcircle(xD, yD, xE, yE, xF, yF);
        
        // 计算交集面积
        double ans = circleIntersectionArea(circle1, circle2);
        // 格式化输出，保留10位小数
        System.out.printf("%.10f", ans);
    }
}

题目内容

二维平面上两个三角形$▲ABC$和三角形$▲DEF$，记它们的外接圆为$O、P$，求解$O$和$P$公共部分的面积。

输入描述

第一行输入六个整数

$x_A,y_A,x_B,y_B,x_C,y_C$$(-100≤x_A,y_A,x_B,y_B,x_C,y_C≤100)$代表$▲ABC$的三个顶点。保证三角形存在

第二行输入六个整数

$x_D,y_D,x_E,y_E,x_F,y_F$$(-100≤x_D,y_D,x_E,y_E,x_F,y_F≤100)$代表$▲DEF$的三个顶点。保证三角形存在

输出描述

在一行上输出一个实数代表两圆的公共面积。

由于实数的计算存在误差，当误差的量级不超过$10^{-6}$时，您的答案都将被接受。具体来说，设您的答案为$a$，标准答案为b，当且仅当$\frac{|a-b|}{max(1,|b|)}≤10^{-6}$时，您的答案将被接受。

样例1

输入

-5 2 -4 3 -1 3
-5 2 -4 3 -1 3

输出

26.7035375555

说明