2021-2022-1 ACM集训队每周程序设计竞赛(5) - 问题 C: 剪切 - 题解

本文主要是介绍2021-2022-1 ACM集训队每周程序设计竞赛(5) - 问题 C: 剪切 - 题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门

    • 分割
      • 题目描述
      • 输入描述
      • 输出描述
      • 样例一
        • 输入
        • 输出
      • 样例二
        • 输入
        • 输出
      • 提示
  • 题目分析
  • AC代码


分割

  • CMP
  • 跳蛙
  • 剪切
  • 数学?
  • 数学!
  • 逃离

时间限制:1秒
空间限制:128M


题目描述

在一个二维坐标平面上,有一个四边形。
它的四个顶点的坐标分别是 ( 0 , 0 ) , ( W , 0 ) , ( W , H ) (0,0),(W,0),(W,H) (0,0),(W,0),(W,H) ( 0 , H ) (0,H) (0,H)

四边形内部(或边界上),有一个点。
它的坐标是 ( x , y ) (x,y) (x,y)

从这个点画一条直线,把四边形分成两个部分。
问你面积最小的那个部分的最大面积是多少。

同时,还要问你得到这个面积的划分方法数。


输入描述

输入一行 4 4 4个空格隔开的正整数,具体意义见题目描述。

输入格式如下:

W H x y

其中:

  • 1 ≤ W , H ≤ 1 0 9 1\leq W,H\leq10^9 1W,H109
  • 0 ≤ x ≤ W 0\leq x\leq W 0xW
  • 0 ≤ y ≤ H 0\leq y\leq H 0yH

输出描述

输出一行空格隔开的两个数

  • 第一个数是划分成的两部分的面积最小的那部分的最大面积,7舍8入保留6位小数。
  • 第二个数代表划分成这个面积的方案,0代表只有一种划分方案,1代表有多种划分方案。

样例一

输入
2 3 1 2
输出
3.000000 0

样例二

输入
2 2 1 1
输出
2.000000 1

提示

样例一中,直线 x = 1 x=1 x=1将四边形划分为面积相等的两块儿,每一块儿的面积都是3,且只有这一种划分方案

题目描述能力有限,不喜勿喷


题目分析

不难发现这个四边形是一个矩形。矩形内一点做一条直线总有方法把矩形划分为面积相等的两部分
因此面积小的那部分的最大值就是矩形面积的一半( W ∗ H / 2 W* H/2 WH/2)。

什么4舍5入7舍8入都是套路,因为面积的一半要么是整数,要么是“ . 5 .5 .5”,保留 6 6 6位小数的话最后一位小数肯定是 0 0 0,因此不需要担心进位问题。

那么还有问题就是有多少种方法可以把矩形分成面积相等的两部分。

一条直线把矩形分成面积相等的两部分,此线必过矩形中心

那么问题迎刃而解:

  • 如果给你的点不是矩形中心,需且只需要做一条经过这个点和矩形中心点的连线就能把矩形划分为面积相等的两部分。
    只有这一种做法,故第二个数输出0。

  • 如果给你的点恰好是矩形中心,那么经过这个点的任意一条直线都经过矩形中心,都能把矩形划分为面积相等的两部分。
    做法有无数种,故第二个数输出1。


AC代码

#include <iostream>
using namespace std;int main() {double a, b, c, d;cin >> a >> b >> c >> d;printf("%.6lf ", a * b / 2);puts(abs(a - c * 2) < 1e-7 && abs (b - d * 2) < 1e-7 ? "1" : "0"); // 其中abs(x)<1e-7可以理解为|x|=0,因为浮点数有精度问题return 0;
}

原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/120897332

这篇关于2021-2022-1 ACM集训队每周程序设计竞赛(5) - 问题 C: 剪切 - 题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/893889

相关文章

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

Java 线程安全与 volatile与单例模式问题及解决方案

《Java线程安全与volatile与单例模式问题及解决方案》文章主要讲解线程安全问题的五个成因(调度随机、变量修改、非原子操作、内存可见性、指令重排序)及解决方案,强调使用volatile关键字... 目录什么是线程安全线程安全问题的产生与解决方案线程的调度是随机的多个线程对同一个变量进行修改线程的修改操

Redis出现中文乱码的问题及解决

《Redis出现中文乱码的问题及解决》:本文主要介绍Redis出现中文乱码的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 问题的产生2China编程. 问题的解决redihttp://www.chinasem.cns数据进制问题的解决中文乱码问题解决总结

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决

Springboot如何正确使用AOP问题

《Springboot如何正确使用AOP问题》:本文主要介绍Springboot如何正确使用AOP问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录​一、AOP概念二、切点表达式​execution表达式案例三、AOP通知四、springboot中使用AOP导出

Python中Tensorflow无法调用GPU问题的解决方法

《Python中Tensorflow无法调用GPU问题的解决方法》文章详解如何解决TensorFlow在Windows无法识别GPU的问题,需降级至2.10版本,安装匹配CUDA11.2和cuDNN... 当用以下代码查看GPU数量时,gpuspython返回的是一个空列表,说明tensorflow没有找到

解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题

《解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题》:本文主要介绍解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4... 目录未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘打开pom.XM

IDEA Maven提示:未解析的依赖项的问题及解决

《IDEAMaven提示:未解析的依赖项的问题及解决》:本文主要介绍IDEAMaven提示:未解析的依赖项的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录IDEA Maven提示:未解析的依编程赖项例如总结IDEA Maven提示:未解析的依赖项例如

Redis分片集群、数据读写规则问题小结

《Redis分片集群、数据读写规则问题小结》本文介绍了Redis分片集群的原理,通过数据分片和哈希槽机制解决单机内存限制与写瓶颈问题,实现分布式存储和高并发处理,但存在通信开销大、维护复杂及对事务支持... 目录一、分片集群解android决的问题二、分片集群图解 分片集群特征如何解决的上述问题?(与哨兵模