2

POJ 1005 - I Think I Need a Houseboat

 2 years ago
source link: https://exp-blog.com/algorithm/poj/poj1005-i-think-i-need-a-houseboat/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
I Think I Need a Houseboat

Fred Mapper 正在考虑在路易斯安那州购买一些土地来建他自己的房子。在研究土地的过程中，他发现，路易斯安那州的土地每年都会被密西西比河侵蚀掉 50 平方里。因为 Fred 希望在这个房子里度过余生，所以他需要知道他的那些土地是否会被侵蚀掉。

在做了更多的调查之后，Fred 发现这些土地是以半圆的形状被侵蚀的。这个半圆所对应的正圆的圆心在坐标原点 (0, 0), 坐标轴 x 轴将这个圆切成两半。在 x 轴下方的区域是河流。在第一年刚开始的时候，这个半圆的面积是 0.

红色为侵蚀方向,蓝色为河水
红色为侵蚀方向,蓝色为河水

红色为侵蚀方向,蓝色为河水

问输入Fred Mapper家的坐标 (x, y)，他家所在的位置什么时候被河水侵蚀。

Fred Mapper 的家 (x, y) 到侵蚀中心 (0, 0) 的距离就是侵蚀半径 R

那么 Area = 1/2 * pi * R 就是侵蚀到 Fred Mapper 家时的侵蚀面积

而侵蚀速度为每年 50

那么侵蚀到Fred Mapper家需要 RestYear = Area / 50 = pi * R / 100 年

又要求从第一年开始计算，最后一年不够一年按一年计算，那么 RestYear + 1 取整就可以了。

Download Link

/*
    Author:     Exp
    Date:       2017-11-29
    Code:       POJ 1005
    Problem:    I Think I Need a Houseboat
    URL:        http://poj.org/problem?id=1005
*/

/*
    根据题意建立数学模型如下：
      位于平面坐标第一二象限的一个半圆从原点(0,0)开始向(x,y)扩散，每次扩散50平方
      求第几次扩散会覆盖到(x,y)， 其中y>0

      勾股定理半径 R^2 = (x-0)^2 + (y-0)^2
      半圆面积公式 Area = pi * R^2 / 2
      当 Area 是 50 整数倍时, 扩散次数 cnt = Area / 50
      当 Area 不是 50 整数倍时, 扩散次数 cnt = Area / 50 + 1    （亦即向上取整）
*/

#include <math.h>
#include <iostream>
using namespace std;

const static double PI = 3.141592654;    // 常量π
const static double HALF_PI = PI / 2;    // 半圆面积公式常量
const static double EACH_AREA = 50;    // 每次扩散面积

/* 
 * 求解扩散次数
 * @param x 扩散坐标x
 * @param y 扩散坐标y
 * return 扩散次数
 */
int diffuse(double x, double y);


int main(void) {
    int testCase = 0;    // 测试用例数
    cin >> testCase;

    for(int i = 1; i <= testCase; i++) {
        double x, y;
        cin >> x >> y;
        int cnt = diffuse(x, y);
        cout << "Property " << i << ": This property will begin eroding in year " << cnt << '.' << endl; 
    }
    cout << "END OF OUTPUT." << endl;

    //system("pause");
    return 0;
}


int diffuse(double x, double y) {
    double R2 = x * x + y * y;
    double Area = HALF_PI * R2;
    return (int) ceil(Area / EACH_AREA);    // 向上取整
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK