10445 - Make Polygon

[mf]

One mistake: you don't clean angle_min and angle_max variables between test cases.

Output for this input should be same as for sample input:

Code: Select all

3
0 10
10 0
0 0

4
0 10
10 10
10 0
0 0

0

[Deci]

Thanks mf, I haven't noticed it. Now this error is corrected but it still give-me WA.
Could the problem be here? angle_total!=(num_punts-2)*180 Maybe some polygon doesn't satisfy this

[mf]

That formula is probably okay, but the way in which you use floating-point numbers is wrong.

Floating-point computations (especially with trig functions) aren't very accurate, and so you shouldn't compare numbers directly. Instead, check whether if the absolute difference is less than some small positive constant (e.g. 1e-9)
More on this topic here.

[Deci]

Thanks mf now I get AC

[helloneo]

Hello..~
My probram passed all the cases on this thread.. but still WA..
I also gave eps when I compare 2 numbers..
Any ideas..?

Code: Select all

#include <stdio.h>
#include <math.h>
#define ERR 1e-9
typedef struct _p {
    double x, y;
} POINT;
int ccw(POINT a, POINT b, POINT c)
{
    double l = (a.x*b.y+b.x*c.y+c.x*a.y) - (a.y*b.x+b.y*c.x+c.y*a.x);
    if (l > 0)
        return 1;
    else if (l < 0)
        return -1;
    return 0;
}
double get_angle(POINT a, POINT b, POINT center)
{
    POINT v1, v2;
    double in_p, s1, s2;
    v1.x = a.x - center.x;
    v1.y = a.y - center.y;
    v2.x = b.x - center.x;
    v2.y = b.y - center.y;
    in_p = v1.x * v2.x + v1.y * v2.y;
    s1 = sqrt(v1.x*v1.x+v1.y*v1.y);
    s2 = sqrt(v2.x*v2.x+v2.y*v2.y);
    return acos(in_p / (s1 * s2));
}
int main()
{
    int n;
    int i, j, k;
    double ang, sum;
    double min1, max1;
    double total_ang;
    double PI = acos(-1.0);
    POINT pt[30];
    while (scanf("%d", &n) == 1 && n >= 3) {
        for (i = 0; i < n; i++) {
            scanf("%lf%lf", &pt[i].x, &pt[i].y);
        }
        pt[n] = pt[0];
        pt[n+1] = pt[1];

        sum = 0.0;
        max1 = 0.0;
        min1 = 999999999.0;

        total_ang = (n-2) * PI;

        /* assume points are in counter-clock wise order.. */
        for (i = 0; i < n; i++) {
            ang = get_angle(pt[i], pt[i+2], pt[i+1]);
            k = ccw(pt[i], pt[i+1], pt[i+2]);
            if (k < 0)
                ang = 2*PI-ang;
            if (ang > max1)
                max1 = ang;
            if (ang < min1)
                min1 = ang;
            sum += ang;
        }
        if (fabs(sum-total_ang) < ERR) {
            min1 = min1 * 180 / PI;
            max1 = max1 * 180 / PI;
            printf("%.6lf %.6lf\n", min1, max1);
            continue;
        }

        /* if not counter-clock wise order */
        sum = 0.0;
        max1 = 0.0;
        min1 = 999999999.0;
        for (i = 0; i < n; i++) {
            ang = get_angle(pt[i], pt[i+2], pt[i+1]);
            k = ccw(pt[i], pt[i+1], pt[i+2]);
            if (k > 0)
                ang = 2*PI-ang;
            if (ang > max1)
                max1 = ang;
            if (ang < min1)
                min1 = ang;
            sum += ang;
        }
        min1 = min1 * 180 / PI;
        max1 = max1 * 180 / PI;
        printf("%.6lf %.6lf\n", min1, max1);
    }
    return 0;
}

[DJWS]

Test cases that some are collected from other threads and some are generated by me.

5
0 0
10 0
15 5
0 20
-15 5
5
-10 0
-10 2
0 1
10 2
10 0
5
10 0
10 2
0 1
-10 2
-10 0
13
0 7
7 0
14 8
3 15
2 9
3 11
4 12
6 11
8 9
9 8
7 6
5 5
3 5
3
0 0
10 0
0 10
4
0 0
10 0
10 10
0 10
6
0 0
1 0
2 0
2 2
1 2
0 2
6
0 0
1 0
1 10
0 5
-1 10
-1 0
20
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
9 1
8 1
7 1
6 1
5 1
4 1
3 1
2 1
1 1
0 1
0

63.434949 161.565051
84.289407 191.421186
84.289407 191.421186
11.309932 270.000000
45.000000 90.000000
90.000000 90.000000
90.000000 180.000000
11.309932 337.380135
90.000000 180.000000