10445 - Make Polygon

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Thu Mar 16, 2006 2:35 pm

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
New poster
Posts: 3
Joined: Thu Mar 16, 2006 12:33 pm

Post by Deci » Fri Mar 17, 2006 1:19 am

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Mar 17, 2006 4:36 pm

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
New poster
Posts: 3
Joined: Thu Mar 16, 2006 12:33 pm

Post by Deci » Fri Mar 17, 2006 11:43 pm

Thanks mf now I get AC

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Sat Oct 14, 2006 11:42 am

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
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Post by DJWS » Tue Jan 29, 2008 5:30 pm

Test cases that some are collected from other threads and some are generated by me. :)
Input wrote: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
Output wrote: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

Post Reply

Return to “Volume 104 (10400-10499)”