[UVA][何] 10445 - Make Polygon＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2014-02-17 08:04:37| 人2,404| 回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;
}