[UVA][幾何] 10445 - Make Polygon
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;
}