24h購物| | PChome| 登入
2014-02-17 08:04:37| 人氣2,191| 回應0 | 上一篇 | 下一篇

[UVA][幾何] 10445 - Make Polygon

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

Problem B

Make Polygon

Input: standard input

Output: standard output

Time Limit: 2 seconds

 

Mr. Picasso is a geometry expert. Recently he invented a method of drawing polygon. He starts with a point and draw a line segment from the end point of the previous line segment in such a way so that except adjacent segments no two segments intersect. He finishes drawing when he returns to the starting point. Such a polygon is shown in the following figure.

 

In this problem you have to find the minimum and maximum angle of Picasso’s polygon.

 

Input

Each input starts with an integer, N (3<=N<=20). In the following N lines there are two integers indicating the Cartesian coordinate of the end points of line segments drawn by Picasso. The absolute value of each co-ordinate will not cross 1000. Input is terminated when N is less than 3.

 

Output

For each line of input print the value of minimum and maximum angles of Picasso’s Polygon in degree. Use 6 digits precision.

 

Sample Input

3
0 0
10 0
0 10
4
0 0
10 0
10 10
0 10
0

 

Sample Output

45.000000 90.000000
90.000000 90.000000

______________________________________________________________________________
 (Problem-setter: Md. Kamruzzaman, BUET Sprinter)

題目描述：

給一個簡單多邊形，求內角的最大最小值為何 ?

給定方式 順時針 或 逆時針 順序都有可能。

題目解法：

首先要搞定到底是順時針還是逆時針，

挑出最邊界的一點，再查找鄰近兩點，將輸入調整成單一順序。

接著利用相鄰兩點所夾的角度，得到該角的角度。

// 用了其他奇怪的做法，一直卡 WA ...

#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;
const double eps = 1e-10;
const double pi = acos(-1);
struct Pt {
    double x, y;
    Pt(double a=0, double b=0):
        x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x - a.x) > eps)
            return x < a.x;
        return y < a.y;
    }    
    Pt operator-(const Pt &a) const {
        Pt ret;
        ret.x = x - a.x;
        ret.y = y - a.y;
        return ret;
    }
};
struct Vec {
    double x, y;
    Vec(double a=0, double b=0):
        x(a), y(b) {}
    Vec(Pt a):
        x(a.x), y(a.y) {}
};
double cross(Vec a, Vec b) {return a.x * b.y - a.y * b.x;}
double dot(Vec a, Vec b) {return a.x * b.x + a.y * b.y;}
double len(Vec a) {return sqrt(a.x * a.x + a.y * a.y);}
double radian2(Vec a, Vec b) {return acos(dot(a, b)/len(a)/len(b));}
double radian2deg(double radian) {return radian / pi * 180;}
int main() {
    for(int n; scanf("%d", &n) == 1 && n >= 3;) {
        int i, j, k;
        Pt D[25];
        for(i = 0; i < n; i++)
            scanf("%lf %lf", &D[i].x, &D[i].y);
        int top_right = 0;
        for(i = 0; i < n; i++) {
            if(D[top_right] < D[i])
                top_right = i;
        }
        if(D[(top_right-1+n)%n].y > D[(top_right+1)%n].y)
            reverse(D, D+n);
        double mndeg = 2 * pi, mxdeg = 0;
        double angle[25];
        for(i = 0; i < n; i++) {
            double vx, vy;
            vx = D[i].x - D[(i-1+n)%n].x;
            vy = D[i].y - D[(i-1+n)%n].y;
            angle[i] = atan2(vy, vx);
        }
        for(i = 0; i < n; i++) {
            double theta = fmod(pi - (angle[i] - angle[(i-1+n)%n]) + 2 * pi, 2 * pi);
            mndeg = min(mndeg, theta);
            mxdeg = max(mxdeg, theta);
        }
        printf("%.6lf %.6lf\n", radian2deg(mndeg), radian2deg(mxdeg));
    }
    return 0;
}

我要檢舉
#10445#Make Polygon#幾何
台長： Morris

您可能對以下文章有興趣

人氣(2,191) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA] 10471 - Can't be too GREEDY
此分類上一篇:[UVA] 10423 - Peter Takes a Tramway

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