24h購物| | PChome| 登入
2013-12-10 08:28:15| 人氣1,921| 回應0 | 上一篇 | 下一篇

[UVA][空間幾何] 10495 - Conic Distance

推薦 0 收藏 0 轉貼0 訂閱站台

Problem D
Conic Distance
Input: standard input
Output: standard output
Time Limit:
2 seconds

A cone is located in 3D such that its base of radius r is in the z = 0 plane with the center at (0,0,0). The tip of the cone is located at (0, 0, h). Two points are given on the cone surface in conic coordinates. The conic coordinates of a point p lying on the surface of the cone are two numbers: the first, d, is the distance from the tip of the cone to p and the second, A < 360, is the angle in degrees between the plane y = 0 and the plane through points (0,0,0), (0,0,h) and p, measured counterclockwise from the direction of the x axis.

Given are two points p1 = (d1, A1) and p2 = (d2, A2) in the conic coordinates. What is the (shortest) distance between p1 and p2 measured on the surface of the cone?

The input is a sequence of lines. Each line contains 6 floating point numbers giving values of: r, h, d1, A1, d2, and A2

For each line of input, output the (shortest) distance between points p1 and p2 on the surface of the cone with the fraction rounded to 2 decimal places.

Sample Input

3.0 4.0 2.0 0.0 4.0 0.0
3.0 4.0 2.0 90.0 4.0 0.0
6.0 8.0 2.14 75.2 9.58 114.3
3.0 4.0 5.0 0.0 5.0 90.0

Sample Output

2.00
3.26
7.66
4.54

Problemsetter: Piotr Rudnicki, University of Alberta
題目描述:

在三維空間中,有一個圓錐體,給兩點在圓錐表面上的點,問這兩點繞著圓錐表面的最短路徑為何?

題目解法:


根據國高中的數學理解,最短路徑即為扇形展開拉直線即為最短距離。
首先要先考慮計算圓錐本身扇形展開於平面上的夾角。

接著將題目給定的兩點,計算到圓心的距離,然後轉換到平面上去。
根據題目給定的表達方式,利用比例的方式轉換到 2D 平面上。

盡可能讓兩點的夾角越小越好。
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
const double pi = acos(-1);
int main() {
    double r, h, d1, A1, d2, A2;
    while(scanf("%lf %lf %lf %lf %lf %lf", &r, &h, &d1, &A1, &d2, &A2) == 6) {
        double ratio = r/hypot(h, r);
        double x1, x2, y1, y2, s1, s2;
        double ret = 1e+30;
        s1 = hypot(h, r)*d1/h;
        s2 = hypot(h, r)*d2/h;
        if(A1 > A2)    swap(A1, A2);
        A2 = min(A2 - A1, 360 - (A2-A1));
        A1 = 0;
        x1 = d1 * cos(2*pi*ratio*(A1/360));
        y1 = d1 * sin(2*pi*ratio*(A1/360));
        x2 = d2 * cos(2*pi*ratio*(A2/360));
        y2 = d2 * sin(2*pi*ratio*(A2/360));
        ret = min(ret, hypot(x1 - x2, y1 - y2));
        swap(A1, A2);
        x1 = d1 * cos(2*pi*ratio*(A1/360));
        y1 = d1 * sin(2*pi*ratio*(A1/360));
        x2 = d2 * cos(2*pi*ratio*(A2/360));
        y2 = d2 * sin(2*pi*ratio*(A2/360));
        ret = min(ret, hypot(x1 - x2, y1 - y2));
        printf("%.2lf\n", ret);
    }
    return 0;
}

台長: Morris
人氣(1,921) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][dp] 10421 - Critical Wave
此分類上一篇:[UVA][greedy] 12520 - Square Garden

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文