Java实现 蓝桥杯 算法训练 Pollution Solution

标签: 蓝桥杯  蓝桥杯VIP

试题 算法训练 Pollution Solution

问题描述
  作为水污染管理部门的一名雇员,你需要监控那些被有意无意倒入河流、湖泊和海洋的污染物。你的其中一项工作就是估计污染物对不同的水生态系统(珊瑚礁、产卵地等等)造成的影响。
在这里插入图片描述

你计算所使用的模型已经在图1中被说明。海岸线(图1中的水平直线)为x轴,污染源位于原点(0, 0)。污染的蔓延呈半圆形,多边形代表了被波及的生态系统。你需要计算出生态系统被污染的面积,也就是图中深蓝色部分。
输入格式
  输入文件包含仅包含一组测试数据。
  每组测试数据第一行为两个整数n (3 <= n <= 100), r (1 <= r <= 1000),n表示了多边形的顶点个数,r表示了污染区域的半径;
  接下来n行,每行包含两个整数xi (-1500 <= xi <= 1500), yi (0 <= yi <=1500),表示每个顶点的坐标,以逆时针顺序给出;
  数据保证多边形不自交或触及自身,没有顶点会位于圆弧上。
输出格式
  输出多边形被圆心位于原点、半径为r的半圆覆盖的面积。
  答案的绝对误差不得超过10^-3。
样例输入
6 10
-8 2
8 2
8 14
0 14
0 6
-8 14
样例输出
101.576437872
数据规模和约定
  存在约30%的数据,n = 3,r <= 20;
  存在另外约30%的数据,n <= 10,r <= 100,坐标范围不超过100;
  存在另外约10%的数据,n <= 100,r <= 150,坐标范围不超过250;
  存在另外约30%的数据,n <= 100,r <= 1000,数据存在梯度;
  对于100%的数据,满足题目所示数据范围。

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;

public class Main {

 static	class vector {
		double x, y;

		public vector(double x, double y) {
			this.x = x;
			this.y = y;
		}

		public vector() {
		}

		public double getLength() {
			return Math.sqrt(x * x + y * y);
		}

		public boolean inCircle(double r) {
			if ((x * x + y * y) <= Math.pow(r, 2)) {
				return true;
			} else {
				return false;
			}
		}

		public double multiplication(vector v) {
			return x * v.y - y * v.x;
		}

		public vector add(vector v) {
			return new vector(x + v.x, y + v.y);
		}
	}

	public static void main(String[] args) throws IOException {
		  run();
	}

	public static double getArea(vector a, vector b, double r) {
		/**
		 * 两个向量a与b的向量积(外积)是一个向量,记作a×b,它的模是|a×b|=|a|*|b|*sinθ
		 */
		double deg = a.multiplication(b) / (a.getLength() * b.getLength());
		deg = Math.asin(deg); // 求出正弦对应的弧度

		// 扇形面积s=1/2*a*r*r(a为弧度)
		return deg * Math.pow(r, 2) / 2; // 向量a,b与圆心形成的弧度的面积

	}

	public static double handle(vector a, vector b, double r) {
		boolean flaga = a.inCircle(r);
		boolean flagb = b.inCircle(r);
		double result = 0;
		if (flaga && flagb) { // 两个点都在圆内
			result = a.multiplication(b) / 2;
		} else { // 两种情况:一个在圆内,一个在圆外;两个点在圆外。
			if (flaga ^ flagb) { // 一个在圆内,一个在圆外
				vector p = a, m = b, mid = null; // 二分法查找线段与圆的交点
				for (int i = 0; i < 20; i++) {
					mid = new vector((p.x + m.x) / 2, (p.y + m.y) / 2);
					if (mid.inCircle(r) == flaga) {
						p = mid;
					} else {
						m = mid;
					}
				}
				if (flaga) { // a点在圆内
					result = a.multiplication(mid) / 2 + getArea(mid, b, r);// 三角形面积+圆弧的面积
				} else {
					result = mid.multiplication(b) / 2 + getArea(a, mid, r);
				}
			} else { // 两个点在圆外。1 、线段穿过在圆内,2、线段不穿过圆内
				vector p = a, m = b, mid = null, newmid = null;
				// 寻找距离远点最近的点
				for (int i = 0; i < 20; i++) {
					mid = new vector((p.x + m.x) / 2, (p.y + m.y) / 2);
					newmid = mid.add(new vector((m.x - p.x) * 0.0001, (m.y - p.y) * 0.0001));
					if (mid.getLength() < newmid.getLength()) {
						m = mid;
					} else {
						p = mid;
					}
				}
				if (mid.inCircle(r)) { // mid在圆内
					result = handle(a, mid, r) + handle(mid, b, r); // 递归
				} else {
					result = getArea(a, b, r);
				}
			}
		}
		return result;
	}

	public static void run() throws IOException {
		// ALGO-164 Pollution Solution
		StreamTokenizer input = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		// Scanner scan = new Scanner(System.in);
		// int n = scan.nextInt();
		// int r = scan.nextInt();
		input.nextToken();
		int n = (int) input.nval;
		input.nextToken();
		int r = (int) input.nval;
		ArrayList<vector> vecList = new ArrayList<vector>();
		for (int i = 0; i < n; i++) {
			input.nextToken();
			double x = input.nval;
			input.nextToken();
			double y = input.nval;
			vecList.add(new vector(x, y));
		}
		double result = 0;
		for (int i = 0; i < n; i++) {
			result += handle(vecList.get(i), vecList.get((i + 1) == n ? 0 : i + 1), r);
		}
		System.out.println(result);
	}
}

版权声明:本文为a1439775520原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/a1439775520/article/details/105508955

智能推荐

SpringBoot 使用freemarker 处理文档,找不到文件位置(报错:basePackagePath=““ /* relatively to resourceLoaderClass pkg)

在Spring Boot中加载word的文档的时候,加载ftl文档的位置应该是从 target目录下面去加载的(不太确定),不是像大多数情况这样根据类的路径去加载。SpringBoot加载的位置应该是从 “resources”文件下面开始,如果放到“resources”的根目录下面需要加一道“/”斜线。 类似于: config...

剑指offer 合并两个排序的链表

题目 链接:https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/ 思路 我想的是,与合并两个有序数组一样的思维,新建一个链表,然后判断谁的值大,进而在新的链表上面进行插入。 看书思路 合并链表是一个递归问题:合并一个节点后可以转化为一个子问题。终止条件是其中一个链表为空 代码 链表反转也可以用递归解决...

Java编程思想 第三章:操作符

Java中的操作符和c/c++中的操作符基本一致,因为我之前学习过C语言和C++,所以本章的内容大部分都已熟知,下面只做简单的介绍。 Java操作符及优先级 Java中的操作符包括算术操作符,关系操作符,逻辑操作符,位运算符、自操作运算符、移位运算符、赋值运算符和其他运算符。 算术操作符:包括加减乘除和取余(%),优先级乘除取余高于加减,都是双元运算符,其中加法(+)可以用来连接两个字符串,比如:...

JetBrains 系列开发工具,如何配置 `SCSS` `File Watcher` ,相关输出配置参数详解:webStorm phpStorm IDEA

JetBrains 系列开发工具,如何配置 SCSS File Watcher ,相关输出配置参数详解:webStorm phpStorm IDEA 前言 你目前已经了解了如何使用 SCSS 进行开发,了解了该文章的内容:『 SCSS 日常用法 』 在 JetBrains 系列开发工具中通过 FileWatcher 进行编译的 SCSS 文件都是通过 sass 这个程序进行的。『 如何添加 Fil...

C语言小函数—二进制与十六进制

测试如下 “` int main() { long int num = 15; } “`...

猜你喜欢

仿微博或微信的文章多图显示(自定义MultiImageView)

按照一般的规矩,先上张图来供大伙看看 如果大致是大伙们需要实现的功能,不烦一观 自定义MultiImageView 工具类 具体使用 app.gradle中添加依赖 implementation 'com.github.bumptech.glide:glide:4.8.0' AndroidManifest.xml中配置联网权限 <uses-permission android:name=&q...

经典进程同步和互斥问题

经典进程同步与互斥问题 前言 一、生产者-消费者问题 1.问题描述 2.问题分析 3.代码 二、读者-写者问题 1.问题描述&&分析 2.代码 三、哲学家进餐问题 1.问题描述&&分析 2.代码 四、理发师问题 1.问题描述&&分析 2.代码 前言 在多道程序设计环境中,进程同步是一个非常重要的问题,下面讨论几个经典的进程同步问题。 一、生产者-消费...

java设计模式——ThreadLocal线程单例

1、定义一个ThreadLocal线程单例,代码如下: 2、定义一个多线程类,代码如下: 3、定义一个测试类,代码如下: 4、输出结果,如下图:...

【tensorflow】线性模型实战

线性模型:y = 1.477 * x + 0.089   1. 采样数据 采样噪声eps在均值0,方差0.01的高斯分布中,而后在均匀分布U(0,1)中,区间[-10,10]进行n=100次随机采样:   2. 计算误差 循环计算每个点的预测值与真是值之间差的平方并累加,从而获得训练集上的均芳误差损失值。   3. 计算梯度   4. 梯度更新 对权重w和偏...

常见损失函数和评价指标总结(附公式&代码)

网上看到一篇很实用的帖子关于常见损失函数和评价指标,收藏下来 本文转载于https://zhuanlan.zhihu.com/p/91511706 ------------------------------------------------------------------------------------------------------------------------------...