10135 - Herding Frosh

[rjhadley]

I am unsure of how to solve this problem - does anyone have an suggestions as to an approach that works?

I know that a convex hull which encloses all the points will give the minimum length of silk needed to wrap around all the points. However, if the telephone poll is not an extreme point then additional silk is needed to come/go from/to the telephone poll and the convex hull. So the optimal solution can deviate from a convex hull...

[reiners]

I'm getting WA for this, but I'm not sure why. Can anyone please give an input for which my program fails and the expected output for that input?

[cpp]#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstdio>

using namespace std;

#define EPSILON 0.000001 /* a quantity small enough to be zero */

#define DIMENSION 2 /* dimension of points */
#define X 0 /* x-coordinate index */
#define Y 1 /* y-coordinate index */

typedef double point[DIMENSION];

#define MAXPOLY 1002 /* maximum number of points in a polygon */

typedef struct {
int n; /* number of points in polygon */
point p[MAXPOLY]; /* array of points in polygon */
} polygon;


point first_point; /* first hull point */

void copy_point(point a, point b)
{
int i; /* counter */

for (i=0; i<DIMENSION; i++) b = a;
}

int leftlower(const void *p1, const void *p2)
{
if ((*(point*)p1)[X] < (*(point*)p2)[X]) return (-1);
if ((*(point*)p1)[X] > (*(point*)p2)[X]) return (1);

if ((*(point*)p1)[Y] < (*(point*)p2)[Y]) return (-1);
if ((*(point*)p1)[Y] > (*(point*)p2)[Y]) return (1);

return(0);
}

void sort_and_remove_duplicates(point in[], int *n)
{
int i; /* counter */
int oldn; /* number of points before deletion */
int hole; /* index marked for potential deletion */

qsort(in, *n, sizeof(point), leftlower);

oldn = *n;
hole = 1;
for (i=1; i<(oldn-1); i++) {
if ((in[hole-1][X] == in[X]) && (in[hole-1][Y] == in[Y]))
(*n)--;
else {
copy_point(in,in[hole]);
hole = hole + 1;
}
}
copy_point(in[oldn-1],in[hole]);
}


double signed_triangle_area(point a, point b, point c)
{
return( (a[X]*b[Y] - a[Y]*b[X] + a[Y]*c[X]
- a[X]*c[Y] + b[X]*c[Y] - c[X]*b[Y]) / 2.0 );
}

bool ccw(point a, point b, point c)
{
return (signed_triangle_area(a,b,c) > EPSILON);
}

bool collinear(point a, point b, point c)
{
return (fabs(signed_triangle_area(a,b,c)) <= EPSILON);
}

double distance(point a, point b)
{
int i; /* counter */
double d=0.0; /* accumulated distance */

for (i=0; i<DIMENSION; i++)
d = d + (a-b) * (a-b);

return( sqrt(d) );
}

int smaller_angle(const void *p1, const void *p2)
{
if (collinear(first_point,*(point*)p1,*(point*)p2)) {
if (distance(first_point,*(point*)p1) <= distance(first_point,*(point*)p2))
return(-1);
else
return(1);
}

if (ccw(first_point,*(point*)p1,*(point*)p2))
return(-1);
else
return(1);
}

void convex_hull(point in[], int n, polygon *hull)
{
int i; /* input counter */
int top; /* current hull size */

if (n <= 3) { /* all points on hull! */
for (i=0; i<n; i++)
copy_point(in,hull->p[i]);
hull->n = n;
return;
}

sort_and_remove_duplicates(in,&n);
copy_point(in[0],first_point);

qsort(&in[1], n-1, sizeof(point), smaller_angle);

copy_point(first_point,hull->p[0]);
copy_point(in[1],hull->p[1]);

copy_point(first_point,in[n]); /* sentinel to avoid special case */
top = 1;
i = 2;

while (i <= n) {
if (!ccw(hull->p[top-1], hull->p[top], in[i]))
top = top-1; /* top not on hull */
else {
top = top+1;
copy_point(in[i],hull->p[top]);
i = i+1;
}
}

hull->n = top;
}


double getPolygonPerimeter(polygon *p) {
double perimeter = 0.0;
for (int i = 0; i < p->n; i++) {
perimeter += distance(p->p[i], p->p[(i + 1) % p->n]);
}

return perimeter;
}

int main (int argc, const char * argv[]) {
point in[MAXPOLY]; /* input points */
polygon hull; /* convex hull */
int n; /* number of points */
int i; /* counter */

int testCaseCnt;
scanf("%d",&testCaseCnt);

for (int j = 0; j < testCaseCnt; j++) {
scanf("%d",&n);
for (i=0; i<n; i++)
scanf("%lf %lf",&in[i][X],&in[i][Y]);

convex_hull(in,n,&hull);

int bestPredecessorIndex = -1;
double bestDist = 0.0;
point origin;
origin[0] = 0.0;
origin[1] = 0.0;
for (int i = 0; i < hull.n; i++) {
double dist =
distance(hull.p[i], origin) +
distance(origin, hull.p[(i + 1) % hull.n]);
if (bestPredecessorIndex == -1 || dist < bestDist) {
bestDist = dist;
bestPredecessorIndex = i;
}
}

polygon hullWithOrigin;
hullWithOrigin.n = hull.n + 1;
for (int i = 0; i <= bestPredecessorIndex; i++) {
copy_point(hull.p[i], hullWithOrigin.p[i]);
}
copy_point(origin,
hullWithOrigin.p[bestPredecessorIndex + 1]);
for (int i = bestPredecessorIndex + 1; i <= hull.n; i++) {
copy_point(hull.p[i], hullWithOrigin.p[i + 1]);
}

double perimeter = getPolygonPerimeter(&hullWithOrigin) + 2.0;
printf("%.2f\n\n", perimeter + 0.005);
}

return 0;
}
[/cpp]

[reiners]

Never mind. I found the problem in my previous posting.

[Observer]

After rejudge, there are only 2 accepted submissions (out of >500) for this problem! What's more, both codes run for >> 1 sec. I wonder what has changed...

Would someone who get Acc please tell me? Thanks in advance.

[Per]

I'm not sure exactly what's the problem, but I know I'm responsible.

I'm not even getting AC with the program I used to generate the output. Maybe there are cases where it's hard to avoid precision errors on an Intel machine (I had only tested the I/O on a Sun, and yes, I've certainly learned that lesson now).

I'm looking into it, so don't worry, whatever the problem is, it will be fixed.

The reason that your code runs longer is that there are more (and bigger, the largest one was 204 points before) test cases. Also, with the previous I/O you could get AC by using the naive and incorrect greedy algorithm (computing convex hull and adding (0,0) at some place on the hull), with the new one that will not work.

[Per]

Well, I managed to find a slightly silly mistake in my code, but none in the output.

If anyone has a code which you think should get AC but instead gets WA, please feel free to send it (or a Win32 or Solaris executable) to me and I'll check it.

[..]

I keep getting WA on this problem, here is my algorithm:

Code: Select all

find the convex hull H = {v_1, v_2, ...., v_c}
if origin is in the hull
    trivial
else
    for each v_i
       assume the slik will run along the convex hull except the edge(v_i, v_{i+1})
       find the mid-point M of v_i and v_{i+1}
       find the convex hull H1 of any points in the triangle (origin, M, v_i)
       find the convex hull H2 of any points in the triangle (origin, M, v_{i+1})
       The length of slik = perimeter of H - length of edge(v_i, v_{i+1}) +
                            perimeter of H1 - length of edge (origin, v_i} + 
                            perimeter of H2 - length of edge (origin, v_{i+1}} +
                            2;
      //special case to handle
      //1. no points in the triangle in finding H1 or H2
      //2. all the points in input are colinear.
    end for
    output the smallest length over all i                                        

Do my algorithm fail for some case??


[Note]
After posting this news for few months, I finally get accepted.
My algorithm is in the correct direction, but the choice of M is not so simple. The point M may NOT be the mid point or the point closet to origin on the segment v_{i}, v_{i+1}. I get accepted by trying all possible M:
1. sort the input points p by angle to origin
2. For every p_{j} and p_{j+1} that lie inside the triangle of (origin, v_{i}, v_{i+1}) I take the the mid point of p_{j} and p_{j+1} as M and do the partial convex hull.

[Per]

Hi!

Figuring out the answer to your question has now taken me roughly an hour (though the answer is quite simple). Good question.

The problem with your algorithm is that your choice of M is not necessarily the optimal choice. For instance, if the origin is very close to v_i, it is better to put M nearer v_i.

For instance, for the case

Code: Select all

7
1 1
-9 1
-9 -9
1 -9
1 -2
1 -4
-3 0.9

Your algorithm (or at least my implementation of it), will answer 42.65, whereas the correct answer is 42.55.

[..]

OH~~~
Thanks for your answer.
I will try to improve my algorithm

[Per]

I am not sure (have not tried to implement or prove it), but I think it should work if you pick M to be the point on the line segment that is closest to the origin. It will handle the case I posted, and other cases I thought of.

[junbin]

Well, I managed to find a slightly silly mistake in my code, but none in the output.

If anyone has a code which you think should get AC but instead gets WA, please feel free to send it (or a Win32 or Solaris executable) to me and I'll check it.

I tried solving this question and this is my algorithm:

1) Find convex hull of existing points union origin.
2) If the convex hull contains origin, then we know origin is outside the convex hull (if we don't add origin). Go to step 5.

3) For each adjacent pair of points, try to add origin to this segment by "pushing" the segment towards origin, but bending where necessary: ie: form 2 partcial convex hulls in the triangle between the two hull points and origin.
4) For each of the new polygon (2 partial convex hull + original hull), find the minimum perimeter polygon. goto step 7

5) Find the convex hull of points (without origin).
6) mindist = minimal of perimieter of convex hull with origin or perimeter of convex hull without origin + 2 * distance of origin to any point on new convex hull. (actually i think this step is never required, but I do it just in case)

7) add 2 to the minimum distance found so far
print answer


I believe my algorithm is correct and I've proved it to myself (though the proof is not formal). however, I keep getting WA. Can Per or someone who has managed to get AC please reply? I need to know if my algorithm is correct.. if it is, can you check my code please? :p



ps:

for the case Per posted:
7
1 1
-9 1
-9 -9
1 -9
1 -2
1 -4
-3 0.9

My code gives 42.55

[Per]

I don't understand your explanation of step 3. How do we "push" the segment, i.e. how do we decide how to bend? And how do we form two partial hulls in one triangle? It feels like you left out the description of some non-trivial choices you have to make.

If you want, you can send me your code and I'll check it. Since so few has managed to get AC, I'm still not sure there isn't any error in my I/O.

[junbin]

I've been trying to solve q 10135 (Herding Frosh) without success. My method seems to be correct, and it works for all my test data, but for some weird reason, it gets WA.

Can someone with AC please run the following test data through their program and give me the results? Thank you!


data input:

Code: Select all

20

105
-23.86 42.90
-5.46 39.89
46.78 18.54
-27.53 49.28
-18.64 27.78
-2.41 -49.70
-42.77 20.60
25.89 -37.15
28.1 -8.61
22.51 -27.50
-19.23 35.57
11.7 -11.0
-13.80 -15.87
22.15 -12.82
-50.12 -24.6
45.58 -31.51
-44.10 -17.31
-24.98 2.49
25.65 -19.94
-30.21 -25.59
-42.23 -13.90
-12.90 47.54
-9.28 14.31
-50.95 -1.43
40.78 20.90
-15.4 -20.27
-44.72 -39.56
-22.10 -40.45
-27.59 35.79
23.81 -19.25
-43.91 36.27
-30.15 4.33
-44.73 6.31
-22.85 -41.26
-47.8 -23.33
-35.89 -2.99
11.53 33.43
-44.5 44.36
28.67 47.84
31.34 38.60
-16.58 42.42
-17.56 -7.85
-8.39 33.17
-41.76 42.60
49.71 -17.74
14.77 -12.28
-19.20 49.93
-37.67 -46.66
1.1 33.15
27.32 35.45
-46.31 32.98
-14.84 44.71
-35.79 -10.62
26.12 -34.41
-5.17 45.43
-7.30 6.91
-14.66 -19.40
40.30 38.47
14.49 -23.66
-24.30 -42.71
37.43 -44.98
21.26 32.17
47.23 39.27
-50.38 46.77
16.19 -10.9
48.64 -45.31
-48.59 -30.12
-44.30 37.1
45.27 -16.72
25.35 39.95
16.4 33.34
-39.8 27.62
-30.25 -37.11
-20.52 40.39
47.27 16.28
-44.98 34.2
-35.98 -23.74
-32.54 39.17
-20.25 31.55
-45.54 3.88
26.52 3.37
-35.7 45.10
-25.19 16.2
1.51 3.14
-24.21 39.97
-24.0 -13.23
16.53 35.81
-40.93 27.97
-38.63 13.78
30.46 23.85
15.99 -25.27
22.5 -4.78
-44.61 -27.29
-20.87 35.53
4.52 -50.2
4.39 -48.27
-44.24 -4.25
4.85 28.6
45.33 -4.92
46.74 -34.35
-16.85 -19.63
6.31 36.49
21.89 -23.9
15.10 31.20
-13.2 -45.67

74
-11.63 -38.93
38.31 39.51
24.17 -25.87
9.17 37.32
-2.93 0.96
-22.70 43.71
-31.67 -33.81
12.43 47.39
-27.81 -6.38
-21.84 -43.66
-28.1 39.43
-4.84 44.88
4.60 48.5
-14.33 -7.1
34.13 8.19
20.65 -46.7
4.85 -7.8
-29.7 -12.67
-18.22 17.81
-35.35 24.50
14.39 -16.79
28.18 2.82
-31.73 34.26
40.72 29.96
-3.29 0.80
-20.5 22.85
-29.34 -49.78
-21.74 -33.48
43.85 47.94
-30.29 -41.43
-10.99 -15.83
39.67 -38.34
-33.64 -46.32
-29.79 -50.46
-46.88 -20.13
4.2 -37.9
8.49 -22.29
-22.68 -44.11
13.45 3.66
-17.55 45.50
30.45 -2.44
11.34 -38.79
46.39 46.65
7.25 5.61
24.85 18.62
16.40 -18.15
-46.64 27.55
36.37 -33.70
3.25 -30.93
-35.72 -50.11
-36.39 -12.10
-47.44 -19.32
6.46 8.71
-48.46 28.84
27.8 -2.27
-35.18 20.25
-1.56 13.57
-2.97 3.72
22.41 48.27
7.62 -17.51
-29.86 -11.35
49.90 -15.44
-50.32 -43.59
36.0 -5.41
36.92 -34.14
-23.11 12.89
37.99 -33.95
35.84 2.46
34.56 0.30
-25.75 44.25
36.87 45.32
13.87 -20.46
29.86 -30.43
-34.18 -32.91

84
16.34 41.53
-39.78 -5.60
-38.32 -13.44
-46.45 4.52
-22.52 -29.13
31.19 20.42
41.16 -29.81
-29.12 -46.48
44.91 44.26
-3.1 25.65
-45.27 -19.23
31.79 9.14
-42.18 -43.0
36.0 -11.93
10.45 -23.89
-28.34 9.26
-12.27 32.70
46.13 16.15
38.75 43.26
-42.86 19.87
29.35 16.92
-46.65 33.46
-4.47 -11.4
-24.74 32.23
-1.85 -18.50
10.4 -5.26
-34.16 49.19
39.58 -38.87
44.43 27.53
-10.4 -21.18
-47.62 -16.93
-15.24 -49.55
32.4 -27.33
-7.64 -10.12
-9.91 -21.69
-23.84 -34.29
-42.83 -32.49
45.8 -44.23
34.32 42.20
2.74 -4.37
40.25 -17.83
-3.85 30.90
-35.40 9.41
-26.56 -42.29
22.95 17.45
24.68 -9.78
-9.96 40.52
31.15 -6.84
-26.88 -9.67
26.56 42.75
43.5 19.99
35.63 -32.3
-10.20 -48.8
29.73 12.98
-22.96 -44.54
-26.37 -27.13
-11.35 -26.50
-17.69 -45.84
-23.26 -14.11
-38.97 23.67
16.99 -48.2
-37.16 49.98
48.73 -32.92
35.31 -39.40
38.5 10.98
-29.13 -3.30
21.43 -12.41
-42.48 -48.35
-49.71 -5.95
30.85 28.95
-46.66 -45.31
17.87 -14.79
-26.40 -22.76
-8.81 -4.31
28.97 4.56
26.8 -19.23
-49.79 -43.50
33.73 -22.3
49.17 -5.37
23.96 -22.46
-50.80 -45.50
-48.61 -21.2
-50.29 12.20
-30.65 41.48

26
12.69 -16.24
19.78 -10.37
15.15 26.6
0.12 7.69
16.71 35.1
-4.26 7.91
30.40 -50.42
-38.8 -25.2
11.8 -38.7
15.54 -31.69
3.95 -37.69
-13.19 -22.84
-12.2 -2.44
-25.65 -36.4
39.65 11.47
-12.11 19.10
-34.1 0.36
0.86 7.51
-31.61 -36.65
0.76 24.98
-13.77 -47.33
40.73 38.92
48.17 19.36
-15.28 46.94
19.28 -36.12
-34.2 20.34

16
43.45 48.79
-40.11 15.4
25.17 23.30
28.94 -41.48
23.88 -37.93
38.21 -43.60
16.69 -10.53
-21.73 22.53
17.70 20.13
1.54 -12.79
23.55 15.36
-41.47 -44.78
-39.86 31.2
-33.61 -48.29
43.81 -28.52
46.81 -32.2

74
7.85 -5.26
-30.69 -47.49
32.13 -50.94
15.39 -20.10
-22.44 3.45
-19.32 -32.88
-34.62 -47.31
-39.25 42.59
20.46 14.64
-27.12 -34.82
15.20 -39.61
11.59 -6.47
28.4 -12.99
-3.51 16.29
-12.63 48.62
28.46 15.33
25.56 11.92
29.20 10.50
19.90 11.38
2.19 10.1
-46.65 -5.8
-27.12 -35.93
-35.27 -25.17
47.34 11.62
-13.18 -23.39
-45.46 24.30
9.24 -10.53
3.74 -30.50
20.29 17.0
26.67 -45.59
-40.58 27.25
35.43 -30.25
-27.35 2.32
-35.43 49.1
-49.28 -12.35
31.75 15.72
-8.0 44.2
-28.69 26.5
41.59 -6.12
6.26 34.0
47.10 -22.1
-25.65 27.42
12.3 -4.11
0.77 -17.45
36.80 -34.44
26.73 20.9
-28.34 -33.9
-23.35 43.66
-23.47 -6.72
1.64 -3.29
-45.52 5.9
26.32 17.47
17.74 -26.52
3.31 -24.50
20.84 35.42
-38.24 37.99
26.49 41.75
-41.94 0.42
48.80 6.59
25.93 -43.57
1.84 -42.56
20.96 37.4
49.14 -9.39
-21.46 -42.79
-39.18 10.37
-36.7 -22.59
-44.88 -12.87
13.14 43.52
-47.13 10.84
-8.21 41.52
26.27 23.30
42.54 45.84
47.58 -8.87
31.57 -31.57

103
31.94 -28.55
-3.67 -39.90
15.69 12.84
10.80 20.66
-25.74 -8.16
-49.90 41.1
22.27 2.27
47.66 -36.27
11.12 42.66
-4.68 -39.76
-8.27 -29.12
15.95 -13.35
-38.33 -48.19
-10.32 29.87
13.6 10.67
31.8 -40.72
-19.85 -24.13
14.38 -19.29
-2.24 37.42
39.75 -20.48
41.42 -10.14
-25.64 -24.22
-16.69 -9.16
10.87 -29.94
44.2 0.11
4.16 -1.12
35.51 39.90
37.62 -21.71
15.90 34.19
-41.25 -40.70
39.7 -29.91
39.43 -24.59
5.54 44.76
19.45 -6.92
8.98 5.70
-40.97 -39.69
-12.69 11.47
-6.56 -41.98
-20.11 -20.6
-30.16 -46.33
-35.32 36.23
13.63 42.34
18.56 -37.99
-37.19 4.9
-39.69 49.16
34.97 -48.71
10.71 44.78
-43.48 -18.81
27.27 4.67
38.13 23.4
-30.16 41.93
-2.70 -14.56
39.80 -22.41
31.90 16.54
34.78 -7.22
-47.79 38.68
-4.28 -25.25
47.34 14.68
-35.68 -32.66
18.90 -14.75
25.94 24.36
40.74 29.14
-47.22 -45.53
10.49 1.61
-26.28 -22.13
-6.67 -6.90
9.2 -29.35
-24.20 -19.32
21.2 16.19
13.91 -30.16
-29.95 -43.89
-17.99 49.24
-36.15 42.45
31.52 41.38
2.10 -22.15
26.1 -49.94
31.92 -17.4
4.81 17.26
-9.86 27.43
23.69 -41.24
-30.82 -7.37
13.32 32.76
-50.83 19.22
20.72 -28.24
-43.57 -49.8
-35.85 47.9
16.87 -5.31
-15.2 11.26
-6.18 -39.6
-9.45 47.71
-46.10 20.71
12.75 23.89
4.87 -50.45
49.43 40.31
-50.88 -13.70
21.36 -19.96
39.14 -27.66
20.33 -38.87
18.82 11.79
-44.51 -18.55
-26.72 8.32
10.95 -27.58
-5.79 32.75

45
-38.99 -50.60
11.8 -17.2
-14.7 40.95
40.68 10.53
-11.78 38.21
-46.2 34.51
34.74 4.5
2.9 11.79
22.42 -48.58
-1.94 -27.90
45.59 -4.88
-25.21 -20.57
31.88 2.47
22.61 -34.25
-1.22 37.82
46.45 -6.57
6.38 19.87
20.8 2.88
0.47 -29.50
27.47 -45.72
-33.40 -37.5
17.63 -5.35
-20.44 -30.80
-46.18 -10.21
-46.66 17.50
-37.80 -15.48
-7.48 30.85
-13.74 -49.50
37.13 -12.99
31.36 36.34
19.19 -29.2
14.57 14.26
8.4 10.51
19.36 37.24
-37.41 39.95
45.32 -18.44
-16.85 42.32
-47.8 4.75
-44.25 4.52
18.89 -18.24
7.30 -35.92
-20.6 -25.69
-48.4 -37.84
-7.47 -34.9
46.34 -11.6

34
-42.65 -38.82
-11.86 -19.6
-6.60 18.42
-29.97 26.85
-33.64 -14.50
-35.19 5.70
-3.67 46.15
-12.47 -24.36
12.36 47.37
-9.82 -6.70
-2.63 -39.55
6.72 -43.25
47.20 28.97
2.71 -39.67
12.1 9.31
25.81 44.27
-49.81 34.12
-43.7 43.49
-20.57 -43.35
-36.6 38.41
26.8 -2.85
43.35 4.26
-31.34 0.85
-27.5 -37.90
1.15 -24.47
-33.27 32.34
-31.58 -42.23
22.63 -29.23
29.43 -50.53
-34.78 39.36
-4.81 -25.17
10.87 37.15
-10.56 26.84
-1.8 -37.17

52
30.68 10.9
-40.11 13.37
-8.86 -6.0
14.18 38.71
8.34 19.65
41.18 42.98
-32.87 12.80
-35.91 37.27
-10.40 37.2
-38.59 0.77
-29.60 46.22
9.44 23.23
30.32 31.16
33.10 -38.51
-34.12 -27.88
-35.17 -15.3
4.77 -6.29
-14.70 25.26
44.74 1.62
-21.71 32.30
14.71 43.90
-21.66 15.29
18.4 -42.53
22.95 1.97
-14.32 21.70
-5.46 -20.14
27.83 -1.96
-11.2 -46.19
-26.5 -4.66
44.88 -7.59
37.17 5.51
2.29 -23.38
-46.58 -40.1
-43.91 -46.68
37.38 -19.3
6.39 -18.20
27.87 31.23
-6.81 -14.70
41.3 -43.61
-29.21 4.54
21.9 -49.2
37.7 38.17
-12.94 -12.61
-6.86 4.59
-12.69 -12.37
-5.47 -16.89
43.16 -46.62
-5.74 -30.74
4.37 34.50
0.99 23.88
-4.3 -39.48
20.46 13.65

32
-44.57 38.62
39.28 -6.11
-41.87 -19.89
42.19 -26.69
46.1 -27.63
17.49 -40.27
-32.89 -7.98
-27.48 17.46
0.81 3.61
-40.9 15.60
-15.96 -4.18
27.39 -16.30
-12.91 49.90
-33.7 -39.97
43.13 -27.95
-32.1 41.25
4.49 -40.7
-36.68 28.54
-3.71 35.99
-16.71 -19.55
-33.96 7.97
1.39 -31.71
30.25 17.26
-14.11 18.74
21.1 -12.67
-46.94 -38.11
48.55 -22.97
14.7 -7.58
36.56 25.50
22.33 12.65
-17.65 3.58
30.70 -26.9

65
29.15 -45.82
29.96 -5.41
36.51 28.72
-14.0 5.98
-38.31 -35.84
31.68 43.5
23.58 4.52
18.88 -4.59
-27.19 37.53
-37.56 23.30
-45.33 -43.59
0.28 11.7
-46.2 7.89
24.65 23.49
39.61 32.56
45.87 -49.36
23.28 30.18
37.22 -41.17
5.52 0.30
-11.56 42.65
23.68 -9.91
-48.82 -30.18
6.41 -44.95
-7.51 38.38
21.20 -2.82
42.22 20.56
24.87 22.88
44.12 15.25
10.6 -16.92
6.46 -1.65
-37.74 43.71
-48.6 -26.19
7.73 8.47
-32.83 21.0
-47.14 -10.35
-46.24 44.41
-45.94 -49.96
-24.86 26.44
-49.40 -42.89
12.82 -25.33
21.65 24.16
5.34 -23.2
34.13 -32.74
12.21 45.65
-2.10 -42.7
-46.30 -34.7
10.17 -34.52
-35.7 -45.32
4.76 13.93
45.3 5.15
7.62 22.10
7.30 34.51
-18.33 -30.26
29.6 35.8
-19.82 33.61
0.7 31.69
-2.81 40.81
-22.18 20.92
12.38 19.44
31.80 26.53
45.41 -47.57
-8.42 49.99
5.14 26.21
9.13 18.98
41.61 -30.82

54
-43.87 36.40
-30.73 31.23
48.87 -28.79
-38.23 -46.84
16.74 -16.73
40.58 -15.32
1.82 21.26
42.20 -50.35
48.23 1.32
36.51 -28.74
-37.32 -37.24
-27.45 20.96
-43.24 17.24
40.97 -44.60
0.39 -8.92
3.55 -11.91
-30.92 -11.78
-36.67 22.26
3.28 28.72
4.34 7.68
42.66 -1.50
41.58 -14.33
-12.53 14.31
-27.91 -50.2
-50.11 -46.20
32.88 -16.68
-4.90 20.62
32.57 19.91
-1.16 -15.92
21.5 -21.42
-7.41 40.82
28.92 38.59
17.95 49.96
18.79 -40.92
-30.33 -7.35
35.79 -42.55
-42.88 27.89
-42.6 39.78
43.18 24.87
49.26 -45.53
-1.59 27.49
1.6 -46.87
-46.73 0.32
-8.66 29.51
45.99 -21.83
31.26 -32.31
-33.0 17.87
11.57 5.74
24.20 40.19
-42.35 -32.45
-25.26 -6.94
-20.83 33.70
-11.63 -7.14
17.29 -31.91

52
-47.24 -29.44
1.40 -36.69
43.93 -4.18
-20.57 6.11
-42.77 10.28
46.25 -47.68
48.73 -28.45
33.96 1.97
-8.98 -20.26
24.64 11.64
43.39 22.59
8.23 -39.91
-17.4 23.13
20.8 -11.10
-32.72 -1.93
1.51 49.10
-18.41 6.85
42.30 -41.86
-13.79 -14.8
34.19 -50.93
-32.77 22.65
22.33 20.94
-11.93 -15.89
-49.88 -23.8
41.7 -12.99
19.42 -4.63
-11.69 29.45
24.48 -36.45
28.49 47.60
16.6 36.47
27.89 -29.11
48.10 -25.21
-18.48 -33.46
22.1 13.24
-34.60 -8.47
44.13 -6.75
-21.74 41.78
-31.28 27.98
-4.13 -3.37
-43.20 34.75
21.19 -15.4
16.12 2.97
33.5 16.92
-42.18 31.11
36.4 42.97
46.3 -15.74
14.19 4.46
44.21 45.0
-25.72 -19.52
-33.77 -48.9
5.59 41.59
34.66 -36.82

76
43.43 43.63
-16.51 -45.45
9.82 -35.24
-33.48 -27.9
11.46 17.91
49.5 39.49
24.58 -25.86
10.34 -35.83
44.82 -4.85
-26.14 -33.6
36.73 -27.64
-41.34 23.39
-13.21 -22.52
32.51 16.80
-47.7 19.80
-47.33 -12.54
10.52 -16.27
26.15 -11.61
5.66 -3.79
-47.43 27.29
5.96 -38.68
-21.30 16.63
49.79 18.31
47.1 30.93
-6.93 -15.57
44.45 -50.26
-33.3 16.34
-50.67 14.97
18.12 49.3
-7.34 -31.15
-34.15 -48.6
-3.28 19.17
49.45 -23.38
30.95 -23.18
-24.23 9.95
-47.95 12.57
-21.10 15.22
-23.52 2.50
-44.56 -3.70
6.5 -17.42
28.49 37.38
-13.55 -2.51
-14.68 -48.27
-33.18 49.24
40.30 40.93
35.76 44.85
-27.41 33.88
-25.22 -50.82
-15.46 45.20
20.15 42.41
49.79 24.98
-6.28 -47.16
-44.14 1.79
-32.96 22.35
-30.12 37.26
10.71 48.53
-27.76 -22.52
30.67 37.5
18.95 4.71
36.14 -48.47
-21.0 -24.48
-19.3 -35.15
-1.9 -13.51
12.42 5.72
44.80 15.99
21.2 10.56
46.58 -30.12
-2.67 -26.32
-38.31 43.64
-24.87 1.42
15.73 -38.26
-16.25 -50.54
-48.98 33.25
-3.8 -10.12
-13.8 -1.88
-17.78 48.89

18
-3.32 43.8
-11.8 -19.20
-6.89 -31.81
-38.60 -36.0
21.61 48.9
29.56 38.44
36.19 14.43
-12.52 -19.71
38.19 -50.77
0.14 47.67
14.48 44.5
42.64 17.41
-10.77 32.62
-47.35 49.70
-18.10 -45.81
-14.13 25.54
45.33 2.39
-40.97 7.60

82
15.17 -41.57
-10.31 28.46
-41.44 -41.71
-45.61 18.88
48.77 2.64
-39.37 -41.9
2.15 46.10
36.25 1.9
-31.55 46.96
-34.19 15.28
-16.48 2.75
44.89 41.92
13.46 7.13
22.31 40.70
4.52 1.40
-42.18 44.17
39.72 20.2
-30.49 4.28
-18.61 45.5
-19.0 42.87
32.77 -50.73
-25.74 1.19
-33.31 -42.92
42.51 -8.35
2.34 -16.63
30.35 49.86
31.47 -10.51
-6.9 -25.13
-17.36 34.34
49.82 -7.97
-30.17 18.55
16.39 -3.4
36.6 40.72
-26.93 2.43
7.74 42.4
11.31 -8.11
45.89 -37.87
-29.69 -29.43
-10.75 -13.21
7.99 14.65
19.56 -8.18
30.39 18.40
-9.5 3.55
-41.83 46.21
-5.1 39.24
-31.52 -13.0
6.72 -34.79
45.46 -5.58
31.47 43.92
28.88 48.16
-42.8 -24.94
-32.79 -8.83
12.38 -35.33
-28.47 -5.7
-4.72 -42.22
-43.95 -7.25
48.46 -5.85
-6.56 46.14
-11.47 -36.12
-35.35 -19.39
-26.65 46.7
8.67 47.5
37.41 -32.38
-29.63 -38.5
49.18 -46.87
-44.58 -34.72
-39.88 -29.0
-22.68 -33.28
-42.49 -17.36
5.31 -3.34
8.46 -2.20
15.64 -46.39
12.29 20.89
44.11 -40.33
-48.97 -1.47
35.92 4.93
44.54 -21.10
-10.52 -2.36
-12.51 -49.56
18.15 23.69
15.44 -2.82
-15.30 -19.36

100
-10.2 -4.16
-27.94 23.59
-4.89 -31.43
-3.53 1.4
-28.80 -11.57
-19.72 -16.87
-20.41 7.57
-20.33 -27.53
31.83 36.47
27.90 -42.82
41.15 6.91
-19.15 -31.34
-25.88 9.62
-23.53 25.5
1.51 -47.88
-22.69 -17.70
38.95 8.6
20.95 -10.40
5.10 -41.13
-29.88 32.7
-24.29 -44.9
-30.71 -17.97
24.82 -38.56
-12.91 -42.18
-26.41 3.23
-33.63 -41.11
-47.78 21.35
-20.23 29.0
40.6 21.27
-25.78 -1.42
14.37 23.91
26.54 38.76
7.25 11.25
-16.47 6.75
-49.21 -19.88
26.76 2.93
32.22 -5.45
7.27 12.18
36.19 29.18
8.9 -36.22
1.48 23.40
-14.0 -28.8
-35.43 30.98
24.98 -9.62
19.79 -32.89
-17.72 -35.3
-43.31 -31.68
-50.11 -24.34
22.15 29.96
-11.75 -4.89
-41.46 -42.94
-11.43 36.86
-34.82 31.89
17.65 -4.75
42.77 34.68
-33.12 15.89
36.29 21.22
8.25 20.96
0.35 -42.4
37.63 -21.43
39.33 -26.73
26.60 48.12
-44.59 15.45
-25.66 21.68
8.93 -11.45
-40.3 -16.7
-46.11 18.56
-16.13 -40.11
2.35 -12.68
25.10 -40.92
-35.80 2.29
-10.25 36.46
5.9 22.95
-40.62 29.1
-15.79 29.79
45.45 19.69
23.91 -35.3
30.67 -27.94
35.44 -14.47
26.43 0.3
-9.81 13.98
23.56 -4.55
-40.40 -17.0
36.12 -3.94
-34.5 -7.6
-45.86 28.95
31.55 -43.28
1.72 -47.16
32.13 -48.82
-34.38 25.48
44.0 -30.47
-28.68 35.65
-3.80 -35.5
18.19 -34.74
20.14 7.99
28.67 36.64
-6.7 29.77
3.60 -44.58
4.59 -20.49
-30.65 -26.60

42
-32.20 -22.84
-31.76 -41.16
-25.75 38.75
30.40 -25.93
16.85 -39.0
26.81 12.53
-27.54 -17.94
7.3 6.36
-26.49 -47.67
-11.1 27.85
41.53 -25.56
14.6 27.94
43.11 -40.74
-10.40 -11.59
43.83 -21.61
46.65 -17.26
49.93 9.35
-16.29 8.44
-34.80 -14.37
22.23 48.13
42.46 -46.89
-47.24 18.36
23.7 13.36
-13.48 18.65
-2.43 -27.1
4.3 -21.56
-48.49 1.35
8.33 16.15
16.83 -29.61
-30.72 -25.51
16.17 15.35
-19.95 -11.21
23.89 -26.83
5.62 18.89
3.49 47.63
25.76 9.67
-32.11 38.7
-7.27 41.68
25.4 12.72
-17.45 -26.59
27.22 40.96
39.47 3.8

81
20.2 -11.75
43.56 -17.50
-29.34 -10.25
-22.41 4.3
8.82 15.95
-11.2 -5.64
-18.49 5.8
-50.63 28.60
-46.94 28.12
-25.34 29.67
-47.87 28.20
-33.55 25.54
20.54 -22.70
-32.50 -7.36
-40.28 26.67
9.76 15.23
-9.2 44.39
-39.72 21.71
-1.75 -14.81
-17.11 45.31
-20.5 28.12
-28.47 -29.98
-4.57 24.18
17.70 -15.64
22.54 -45.9
43.48 25.66
-1.27 -21.61
-33.87 31.35
-20.64 -21.73
43.72 -8.51
-18.63 16.15
13.22 3.84
38.77 -24.75
-38.40 6.53
44.69 23.12
-39.60 47.72
9.59 48.8
20.1 24.99
8.74 16.10
39.11 35.88
28.1 21.90
-42.26 30.38
23.31 34.89
4.10 -39.44
-42.18 49.68
44.13 31.45
-36.19 41.57
35.16 46.78
-16.52 8.8
-29.84 -38.22
29.41 27.44
37.14 36.53
19.69 -1.7
-44.86 -20.93
41.26 6.8
41.14 3.58
-3.60 -49.82
43.92 -32.9
-50.27 17.31
1.50 40.4
-19.40 14.78
-3.99 35.45
30.22 26.18
-2.83 -30.30
-44.52 -34.64
13.29 14.2
-21.16 22.2
37.97 37.99
35.60 8.35
7.30 -37.5
22.36 18.39
48.2 14.99
-47.56 -31.9
23.73 -35.4
6.37 -45.10
-15.33 -6.42
-28.56 -2.30
27.56 29.75
6.97 -3.23
29.49 -1.66
-22.1 -25.68

my output:

Code: Select all

446.29

415.79

431.45

353.17

370.65

418.96

447.29

387.33

385.22

413.12

361.07

432.56

430.20

418.83

436.41

394.03

437.09

401.67

387.44

414.64

[horape]

I haven got AC yet, and have some discrepances with your data. As your datasets are so big I haven't given the effort needed to check the data. If you check it, please let me know what are the results.

Code: Select all

413.12  <- 410.59
  (0,0) (-10.4,37.2) (-29.6,46.22) (-35.91,37.27)
  (-40.11,13.37) (-46.58,-40.1) (-43.91,-46.68) (21.9,-49.2)
  (43.16,-46.62) (44.88,-7.59) (44.74,1.62) (41.18,42.98)
  (14.71,43.9) (4.37,34.5) (0.99,23.88) (0,0)

432.56  <- 430.86
  (0,0) (6.46,-1.65) (18.88,-4.59) (29.96,-5.41) (45.3,5.15)
  (44.12,15.25) (39.61,32.56) (31.68,43.5) (-8.42,49.99)
  (-46.24,44.41) (-49.4,-42.89) (-45.94,-49.96)
  (45.87,-49.36) (41.61,-30.82) (23.68,-9.91) (0,0)

430.20  <- 427.50
  (0,0) (-20.83,33.7) (-42.6,39.78) (-43.87,36.4)
  (-46.73,0.32) (-50.11,-46.2) (-27.91,-50.2) (42.2,-50.35) 
  (49.26,-45.53) (48.23,1.32) (43.18,24.87) (17.95,49.96)
  (-7.41,40.82) (-8.66,29.51) (0,0)

401.67  <- 392.03
 (0,0) (-6.7,29.77) (-10.25,36.46) (-11.43,36.86) 
 (-28.68,35.65) (-45.86,28.95) (-47.78,21.35) 
 (-50.11,-24.34) (-41.46,-42.94) (1.51,-47.88) 
 (32.13,-48.82) (44,-30.47) (45.45,19.69) (42.77,34.68)
 (26.6,48.12) (1.48,23.4) (0,0)

[Per]

50% of the currently accepted solutions get the same answers as horape.