[UVA][幾何] 10445 - Make Polygon＠Morris' Blog

2014-02-17 08:04:37| 人氣2,130| 回應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

0 0

10 0

0 10

0 0

10 0

10 10

0 10

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

您可能對以下文章有興趣

[UVA][Knuth'sPermutation] 110 - Meta-Loopless Sorts

[UVA][凸包交集] 137 - Polygons

[UVA] 227 - Puzzle

[UVA] 10895 - Matrix Transpose

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

回應(0)