荒岛探测
题目描述
科学家小蓝来到了一个荒岛，准备对这个荒岛进行探测考察。
小蓝使用了一个超声定位设备来对自己进行定位。为了使用这个设备，小蓝需要在不同的点分别安装一个固定的发射器和一个固定的接收器。小蓝手中还有一个移动设备。定位设备需要从发射器发射一个信号到移动设备，移动设备收到后马上转发，最后由接收器接收，根据这些设备之间传递的时间差就能计算出移动设备距离发射器和接收器的两个距离，从而实现定位。
小蓝在两个位置已经安装了发射器和接收器，其中发射器安装在坐标 (xA, yA) ，接收器安装在坐标 (xB, yB)小蓝的发射器和接收器可能在岛上，也可能不在岛上。
小蓝的定位设备设计有些缺陷，当发射器到移动设备的距离加上移动设备到接收器的距离之和大于 L 时，定位设备工作不正常。当和小于等于 L 时，定位设备工作正常。为了安全，小蓝只在定位设备工作正常的区域探测考察。
已知荒岛是一个三角形，三个顶点的坐标分别为 (x1, y1), (x2, y2), (x3, y3)
请计算，小蓝在荒岛上可以探测到的面积有多大？
输入描述
输入的第一行包含五个整数，分别为xA, yA, xB, yB, L
第二行包含六个整数，分别为x1, y1, x2, y2, x3, y3
保证发射器的两个坐标不同，并且
-1000<=xA, yA, xB, yB , L, x1, y1, x2, y2, x3, y3<=1000
输出描述
输出一行，包含一个实数，四舍五入保留 2 位小数，表示答案。
考虑到计算中的误差，只要你的输出与参考输出相差不超过 0.01 即可。
输入输出样例
示例
输入
10 6 4 12 12
0 2 13 2 13 15
输出
39.99
样例说明
运行限制 最大运行时间：1s 最大运行内存: 256M
C++
暴力算法，最后超时了5555
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int x1, y01, x2, y2, x3, y3, xA, yA, xB, yB, L; double fxy(int a,int b ,double x)//求直线方程 { int X1 = 0, Y1 = 0, X2 = 0, Y2 = 0; switch (a) { case 1:X1 = x1; Y1 = y01; break; case 2:X1 = x2; Y1 = y2; break; case 3:X1 = x3; Y1 = y3; break; default:X1 = xA; Y1 = yA; } switch (b) { case 1:X2 = x1; Y2 = y01; break; case 2:X2 = x2; Y2 = y2; break; case 3:X2 = x3; Y2 = y3; break; default:X2 = xB; Y2 = yB; } return double(Y2 - Y1) / (X2 - X1)*(x - X1) + Y1; } bool island(double x,double y)//判断是否在三角形内 { return ((fxy(1, 2, x) - y)*(fxy(1, 3, x) - y) <= 0) + ((fxy(1, 2, x) - y)*(fxy(2, 3, x) - y) <= 0) + ((fxy(1, 3, x) - y)*(fxy(2, 3, x) - y) <= 0)>=2; } bool ellipse(double x,double y)//判断在椭圆内 { return sqrt((x - xA)*(x - xA) + (y - yA)*(y - yA)) + sqrt((x - xB)*(x - xB) + (y - yB)*(y - yB)) <= L; } int main() { cin >> xA >> yA >> xB >> yB >> L; cin >> x1 >> y01 >> x2 >> y2 >> x3 >> y3; double x, y, cx, cy, S = 0; cx = (xA + xB) / 2.0; cy = (yA + yB) / 2.0; for (x = cx - L/2.0; x <= cx + L/2.0; x += 0.02) for (y = cy-L/2.0; y<=cy+L/2.0; y += 0.005) if (island(x, y)&& ellipse(x, y)) S += 0.0001; printf("%.2f", S + 0.005); return 0; }
