218 - Moth Eradication

[ithamar]

I put the case that yarin suggest with my accepted program and i get

Region #1:
(1.0,1.0)-(1.0,4.0)-(1.0,3.0)-(1.0,2.0)-(1.0,5.0)-(2.0,5.0)-(3.0,5.0)-(4.0,5.0)-(5.0,5.0)-(2.0,2.0)-(3.0,3.0)-(4.0,4.0)-(1.0,1.0)
Perimeter length = 23.31

Is this answer wrong?

[Yarin]

It certainly looks very wrong!! Just look at the vertices, draw them out on a paper. They're not in clockwise order (as the output specification require) and the perimeter length becomes wrong as well. Really strange that you got it accepted, either you were lucky with the testcases or the automatic judge _only_ compares the set of vertices output without taking the order in regard.

[ithamar]

I draw the example and you are absolutly right. My solution is very wrong . I will try to fix it. I already know where the problem is.

Thanxs yarin.

About mi luck i think that the judge data does not contain a case with more than 3 colinear points that is wher my solution is wrong. To avoid possible future problems in rejudgments i will fix it to handle case like this.

[Ramiel]

I send it & get signal 11 (SIGSEGV). Meaning: Invalid memory referenceBut I can't try it out.
Could anyone tell me why??
thanx!!

It's my code :

[c]
#include <stdio.h>
#include <stdlib.h> /* calloc & free */
#include <math.h> /* sqrt & pow*/

typedef struct{
double x, y;
}point;

typedef enum {COUNTER_CLOCKWISE, COLLINEAR, CLOCKWISE} status;

void get_points(point P[], const int num_P);
int find_largest_y(const point P[], const int num_P);
int find_smallest_y(const point P[], const int num_P);
int find_smallest_angle(const point P[], const int num_P,
const int start, const char mode);
status get_turn_way(const point P[], const int a, const int b, const int
c);
double cross_product(const double vector[][2]);
void print_result(const point P[], const int S[],
const int top, const int region_num);
double get_perimeter(const point P[], const int S[], const int top);
double get_distance(const point P[], const int a, const int b);

int main(void)
{
int region_num = 1, i, num_P, count,
high, low, start, next, *CH;
char mode;
point *P;

scanf("%d", &num_P);
while(num_P != 0){
P = (point *)calloc(num_P, sizeof(point));
CH = (int *)calloc(num_P * 2, sizeof(int));

get_points(P, num_P);

high = find_largest_y(P, num_P);
low = find_smallest_y(P, num_P);

count = 0;
for(i = 0; i < num_P; i++)
if(i != low)
next = i;

mode = 'U';
start = low;
CH[0] = low;

if(num_P != 1){
while(next != low){
next = find_smallest_angle(P, num_P, start, mode);

count += 1;
CH[count] = next;
start = next;

if(high == start)
mode = 'D';
}
}
print_result(P, CH, count, region_num);

free(CH);
free(P);

region_num += 1;
scanf("%d", &num_P);
}

return 0;
}

void get_points(point P[], const int num_P)
{
int i;

for(i = 0; i < num_P; i++)
scanf("%lf %lf", &P.x, &P.y);
}

int find_largest_y(const point P[], const int num_P)
{
int i, largest;

largest = 0;
for(i = 1; i < num_P; i++)
if(P.y > P[largest]. y)
largest = i;
else if(P. y == P[largest]. y){
if(P.x < P[largest].x)
largest = i;
}

return largest;
}

int find_smallest_y(const point P[], const int num_P)
{
int i, smallest;

smallest = 0;
for(i = 1; i < num_P; i++)
if(P.y < P[smallest]. y)
smallest = i;
else if(P. y == P[smallest]. y){
if(P.x < P[smallest].x)
smallest = i;
}

return smallest;
}

int find_smallest_angle(const point P[], const int num_P,
const int start, const char mode)
{
int i, smallest;

if(mode == 'U'){
for(i = 0; i < num_P; i++)
if((P.x != P[start].x || P.y != P[start].y) && P[start].y <=
P[i].y){
smallest = i;
break;
}

for(i = 0; i < num_P; i++)
if(i != start && smallest != start && P[start].y <= P[i].y){
if(get_turn_way(P, start, smallest, i) == CLOCKWISE)
smallest = i;
else if(get_turn_way(P, start, smallest, i) == COLLINEAR)
if(get_distance(P, start, i) < get_distance(P, start, smallest))
smallest = i;
}
}else if(mode == 'D'){
for(i = 0; i < num_P; i++)
if((P[i].x != P[start].x || P[i].y != P[start].y) && P[start].y >=
P[i].y){
smallest = i;
break;
}
for(i = 0; i < num_P; i++)
if(i != start && smallest != start && P[start].y >= P[i].y){
if(get_turn_way(P, start, smallest, i) == CLOCKWISE)
smallest = i;
else if(get_turn_way(P, start, smallest, i) == COLLINEAR)
if(get_distance(P, start, i) < get_distance(P, start, smallest))
smallest = i;
}
}

return smallest;
}

status get_turn_way(const point P[], const int a, const int b, const int
c)
{
double vector[2][2];

vector[0][0] = P[c].x - P[a].x;
vector[0][1] = P[c].y - P[a].y;
vector[1][0] = P.x - P[a].x;
vector[1][1] = P.y - P[a].y;

if(cross_product(vector) < 0)
return COUNTER_CLOCKWISE;
else if(cross_product(vector) > 0)
return CLOCKWISE;
else
return COLLINEAR;
}

double cross_product(const double vector[][2])
{
return vector[0][0] * vector[1][1] - vector[1][0] * vector[0][1];
}

void print_result(const point P[], const int S[],
const int top, const int region_num)
{
int i;

printf("Region #%d:\n", region_num);

for(i = top; i >= 0; i--)
if(i != 0)
printf("(%.1lf, %.1lf)-", P[S[i]].x, P[S[i]].y);
else{
printf("(%.1lf, %.1lf)", P[S[top]].x, P[S[top]].y);
printf("\n");
}

printf("Perimeter length = %.2f\n", get_perimeter(P, S, top));
}

double get_perimeter(const point P[], const int S[], const int top)
{
int i;
double sum = 0;

for(i = top; i > 0; i--)
sum += get_distance(P, S[i], S[i - 1]);
sum += get_distance(P, S[top], S[0]);

return sum;
}

double get_distance(const point P[], const int a, const int b)
{
return sqrt(pow(P.x - P[a].x, 2) + pow(P.y - P[a].y, 2));
}

[/c]

[Dominik Michniewski]

Try to avoid all free() or delet commands in your program ....
I had similar problem - if I remove free() statement from my code everything was OK. strange - I think that it's problem with garbage collector on OJ system ...

Best regards
Dominik

[lhp]

I have tried all test cases on this board, but still got WA...
Could someone help me, please?
thanx!

[c]
#include <stdio.h>
#include <stdlib.h> /* for calloc() */
#include <math.h> /* for sqrt() */
#define POS 1 /* sign(+) */
#define NEG -1 /* sign(-) */

typedef float REAL;
typedef struct node{ /* A trap */
REAL x; /* coordinates */
REAL y;
int if_in; /* indicate whether the nod is in the hull or not */
}trap_t;

int cross(REAL x1, REAL y1, REAL x2, REAL y2)
{ /* determin the sign of the cross product of the two vectors
return POS is positive, NEG if negative, 0 if cross product = 0 */
if(x1 * y2 - x2 * y1 < 0)
return NEG;
else if(x1 * y2 - x2 * y1 > 0)
return POS;
else
return 0;
}

REAL distance(trap_t *a, trap_t *b)
{ /*input two nodes, return their distance; return -1 on error */
REAL tmp;
if(a == NULL || b == NULL)
return -1;
tmp = (a->x - b->x) * (a->x - b->x) + (a->y - b->y) * (a->y - b->y);
return ((REAL) sqrt(tmp));
}

trap_t *next_node(trap_t *node, trap_t *set, int size, int sign)
{ /* input a node on the convex hull, a set of nodes,
the size of the set, and the sign (POS or NEG) on x-axis,
return the pointer to the node next to it on convext hull, NULL on error */
int i;
REAL x, y, /* (x,y) for positive or negative x-axis */
x1, y1, /* (x1,y1) and (x2,y2) for two vectors */
x2, y2;
trap_t *next_node, *temp;

if(sign != POS && sign != NEG)
return NULL;
x = (REAL) sign;
y = 0;

/*find a point to start finding*/
for(i = 0; i < size; i++) {
if(set.if_in == 0) {
next_node = &set;
break;
}
}
x1 = next_node->x - node->x;
y1 = next_node->y - node->y;

for(i = 1; i < size; i++) {
if(set.if_in == 1 || next_node == &set)
continue;
temp = &set;
x2 = temp->x - node->x;
y2 = temp->y - node->y;
if(cross(x, y, x2, y2) <= 0) {
if(cross(x1, y1, x2, y2) > 0) {
next_node = temp;
x1 = next_node->x - node->x;
y1 = next_node->y - node->y;
} else if(cross(x1, y1, x2, y2) == 0) {
if(distance(temp, node) < distance(next_node, node)) {
next_node = temp;
x1 = next_node->x - node->x;
y1 = next_node->y - node->y;
}
}
}
}
next_node->if_in = 1;
return next_node;
}

int main()
{
int cases = 0, size;
int i;
trap_t *set, /* pointer to the array of input nodes*/
*trapL, /* the lowest trap */
*trapH, /* the highest trap*/
*node, *temp;
REAL length;
while(scanf("%d", &size) != 0 && size != 0) {
cases++;
/* input traps*/
set = (trap_t *) calloc(sizeof(trap_t), size);
for(i = 0; i < size; i++) {
scanf("%f %f", &(set.x), &(set.y));
set.if_in = 0;
}
printf("Region #%d:\n", cases);

/* find the lowest and higest traps */
trapL = trapH = &set[0];
for(i = 0; i < size; i++) {
if(trapL->y > set.y)
trapL = &set;
if(trapH->y < set[i].y)
trapH = &set[i];
}

/* find the convex hull */
length = 0;
node = trapL;
trapL->if_in = 1;
while(temp != trapH) { /*left half*/
temp = next_node(node, set, size, NEG);
printf("(%.1f,%.1f)-", node->x, node->y);
length += distance(temp, node);
node = temp;
}

trapL->if_in = 0;
while(temp != trapL) { /*right half*/
temp = next_node(node, set, size, POS);
printf("(%.1f,%.1f)-", node->x, node->y);
length += distance(temp, node);
node = temp;
}
printf("(%.1f,%.1f)\n", trapL->x, trapL->y);
printf("Perimeter length = %.2f\n\n", length);
free(set);
}
return 0;
}

[/c]

[Even]

all the case above I get the reasonable answer...

but still WA...can you give me more test case???

[Jucovschi Constantin]

Hello

I've tested all tests that were on the previous pages and all are correct. I don't understand why I get WA

[c]#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <stdlib.h>

#define max 50000

typedef struct
{
float x,y;
} point;

int n, first, choosen, k, region=0, i;
point reper, a[max], c[max];
float lenght;

float dist(point a, point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int surf(point a, point b, point c)
{
float s = (a.x*b.y-a.y*b.x) + (b.x*c.y-b.y*c.x) + (c.x*a.y-c.y*a.x);
if (s>0) return 1; else
if (s==0)
{
if (dist(a,b)<dist(a,c)) return 1; else return -1;
}
return -1;
}

int comp_reper(const void *a, const void *b)
{
return surf(reper, *((point *) a), *((point *)b));
}

int main(void)
{
int i;
while (1)
{
region ++;
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
scanf("%d", &n);first = 1;
if (n==0) break;
for (i=0; i<n; i++)
{
scanf("%f %f", &a.x, &a.y);
if (a.x<reper.x || a.x==reper.x && a.y<reper.x || first)
{ reper = a; choosen = i;first = 0;}
}
for (i=choosen; i<n; i++) a=a[i+1]; n--;
qsort(a,n,sizeof(point),comp_reper);
c[0]=reper;c[1]=a[0];k=1;
for (i=1; i<n; i++)
{
while (1)
{
if (surf(c[k-1], c[k], a) != 1)
{
k++; c[k]=a;
break;
} else
k--;
}
}
k++; c[k]=c[0];
lenght = 0;
printf("Region #%d:\n", region);
for (i=0; i<k; i++)
{
printf("(%0.1f,%0.1f)-", c.x, c[i].y);
lenght+=dist(c[i],c[i+1]);
}
printf("(%0.1f,%0.1f)\n", c[k].x, c[k].y);
printf("Perimeter length = %0.2f\n\n", lenght);
}
return 0;
}[/c]

[lowai]

very confused.

[pascal]
const
maxn = 100;
type
tpoint = record
x, y : real;
end;
var
n, top, caseno : integer;
list : array[0..maxn]of tpoint;
stk : array[1..maxn]of integer;

procedure swap(var a, b : tpoint);
var t : tpoint;
begin
t := a; a := b; b := t;
end;

function multi(var p1, p2, p0 : tpoint) : real;
begin
multi := (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
end;

function comp(var p1, p2 : tpoint) : boolean;
var t : real;
begin
t := multi(p1, p2, list[0]);
if (t > 0) or (t = 0) and
(sqr(p1.x - list[0].x) + sqr(p1.y - list[0].y) <
sqr(p2.x - list[0].x) + sqr(p2.y - list[0].y)) then
comp := true
else
comp := false;
end;

procedure sort(p, r : integer);
var i, j : integer;
x : tpoint;
begin
if r - p + 1 <= 5 then
begin
for j := p + 1 to r do
begin
i := j;
while(i > 1) and comp(list, list) do
begin
swap(list, list);
dec(i);
end;
end;
end
else
begin
x := list[(p + r) div 2];
i := p;
j := r;
repeat
while comp(list, x) do inc(i);
while comp(x, list[j]) do dec(j);
if i < j then swap(list, list[j]);
until i >= j;
sort(p, j);
sort(i + 1, r);
end;
end;

procedure init;
var i : integer;
begin
readln(n);
if n = 0 then halt;
for i := 0 to n - 1 do
begin
readln(list.x, list.y);
if (list.y < list[0].y) or (list.y = list[0].y) and
(list[i].x < list[0].x) then swap(list[0], list[i]);
end;
sort(1, n - 1);
end;

procedure graham;
var i : integer;
ans : real;
begin
for i := 1 to 3 do stk[i] := i - 1;
top := 3;
for i := 3 to n - 1 do
begin
while (top > 1) and (multi(list[i], list[stk[top]], list[stk[top - 1]]) >= 0) do
dec(top);
inc(top);
stk[top] := i;
end;
writeln('Region #', caseno, ':');
ans := 0;
write('(', list[stk[1]].x : 0 : 1, ',', list[stk[1]].y : 0 : 1, ')');
for i := 2 to top do
begin
write('-(', list[stk[i]].x : 0 : 1, ',', list[stk[i]].y : 0 : 1, ')');
ans := ans + sqrt(sqr(list[stk[i]].x - list[stk[i - 1]].x) + sqr(list[stk[i]].y - list[stk[i - 1]].y));
end;
writeln('-(', list[stk[1]].x : 0 : 1, ',', list[stk[1]].y : 0 : 1, ')');
ans := ans + sqrt(sqr(list[stk[top]].x - list[stk[1]].x) + sqr(list[stk[top]].y - list[stk[1]].y));
writeln('Perimeter length = ',ans : 0 : 2);
end;

procedure outspecial;
var ans : real;
begin
writeln('Region #', caseno, ':');
write('(', list[0].x : 0 : 1, ',', list[0].y : 0 : 1, ')');
writeln('-(', list[1].x : 0 : 1, ',', list[1].y : 0 : 1, ')');
ans := sqrt(sqr(list[1].x - list[0].x) + sqr(list[1].y - list[0].y));
writeln('Perimeter length = ',ans : 0 : 2);
end;

begin
caseno := 0;
while true do
begin
inc(caseno);
init;
if caseno > 1 then writeln;
if n > 2 then graham else outspecial;
end;
end.
[/pascal][/pascal]

[oriol78]

hi everybody, i'm trying to solve the problem 218 but judge always replies me WA, this is my code and my tests:

[cpp]
/* @JUDGE_ID: xxxxxxx 218 C++ */
/* @BEGIN_OF_SOURCE_CODE */

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <math.h>
#include <stdio.h>
using namespace std;

int _case;

int nextA(int pos, vector<pair< double, double> > points)
{

int res = pos+1;
for(int i = pos+2; i < points.size(); i++)
{

if(((points.second-points[pos].second)/(points.first-points[pos].first)) >
((points[res].second-points[pos].second)/(points[res].first-points[pos].first)))
res = i;
}

return res;
}

int nextB(int pos, vector<pair< double, double> > points)
{
int res = pos-1;
for(int i = pos-2; i >= 0 ; i--)
{
if(((points.second-points[pos].second)/(points.first-points[pos].first)) >
((points[res].second-points[pos].second)/(points[res].first-points[pos].first)))
res = i;
}
return res;
}

void printar(vector<pair< double, double> > points)
{
for(int i = 0; i < points.size(); i++)
cout << points.first << " " << points.second << endl;
}

double dist(pair<double,double> x, pair<double,double> y)
{
return sqrt(((y.second-x.second)*(y.second-x.second))+((y.first-x.first)*(y.first-x.first)));
}

double perim(vector<pair< double, double> > points, vector<int> sor)
{
double res = 0;
for(int i = 0 ; i < sor.size()-1; i++)
res += dist(points[sor],points[sor[i+1]]);
return res;
}

void calc(vector<pair< double, double> > points)
{
vector<int> sor;
sort(points.begin(),points.end());
int pos = 0;
sor.push_back(0);
while(pos != points.size()-1)
{
pos = nextA(pos,points);
sor.push_back(pos);
}
while(pos != 0)
{
pos = nextB(pos,points);
sor.push_back(pos);
}
if(points.size() == 1)
sor.push_back(pos);
cout << "Region #"<< _case++ << ":"<< endl;
printf("(%.1f,%.1f)",points[sor[0]].first,points[sor[0]].second);
for(int i = 1; i < sor.size(); i++)
printf("-(%.1f,%.1f)",points[sor].first,points[sor].second);
cout << endl;
printf("Perimeter length = %.2f",perim(points,sor));
cout << endl;
cout << endl;
}

void proces(int num)
{
vector<pair< double, double> > points(num);
for(int i = 0; i < num; i++)
cin >> points.first >> points[i].second;
calc(points);
}

int main()
{
int num;
cin >> num;
_case = 1;
while(num)
{
proces(num);
cin >> num;
}
return 0;
}
/* @END_OF_SOURCE_CODE */
[/cpp]

input

3
1 2
4 10
5 12.3
6
0 0
1 1
3.1 1.3
3 4.5
6 2.1
2 -3.2
7
1 0.5
5 0
4 1.5
3 -0.2
2.5 -1.5
0 0
2 2
6
0 0
1 1
2 2
3 3
0 3
1 2
1
5 5
2
1 1
5 6
12
1 1
1 4
1 3
1 2
1 5
2 5
3 5
4 5
5 5
2 2
3 3
4 4
9
0 1
5 0
4 1.5
3 -0.2
0 -1
2.5 -1.5
0 0
2 2
6 0
0

ouput

Region #1:
(1.0,2.0)-(4.0,10.0)-(5.0,12.3)-(1.0,2.0)
Perimeter length = 22.10

Region #2:
(0.0,0.0)-(3.0,4.5)-(6.0,2.1)-(2.0,-3.2)-(0.0,0.0)
Perimeter length = 19.66

Region #3:
(0.0,0.0)-(2.0,2.0)-(4.0,1.5)-(5.0,0.0)-(2.5,-1.5)-(0.0,0.0)
Perimeter length = 12.52

Region #4:
(0.0,0.0)-(0.0,3.0)-(3.0,3.0)-(2.0,2.0)-(1.0,1.0)-(0.0,0.0)
Perimeter length = 10.24

Region #5:
(5.0,5.0)-(5.0,5.0)
Perimeter length = 0.00

Region #6:
(1.0,1.0)-(5.0,6.0)-(1.0,1.0)
Perimeter length = 12.81

Region #7:
(1.0,1.0)-(1.0,2.0)-(1.0,3.0)-(1.0,4.0)-(1.0,5.0)-(2.0,5.0)-(3.0,5.0)-(4.0,5.0)-(5.0,5.0)-(4.0,4.0)-(3.0,3.0)-(2.0,2.0)-(1.0,1.0)
Perimeter length = 13.66

Region #8:
(0.0,-1.0)-(0.0,0.0)-(0.0,1.0)-(2.0,2.0)-(4.0,1.5)-(6.0,0.0)-(2.5,-1.5)-(0.0,-1.0)
Perimeter length = 15.16


can anybody help sme plz? thx

[oriol78]

4
0 0
0 1
1 1
1 0

[Julien Cornebise]

Hi

I'm opening a new topic about 218 (Moth Eradication) in order to clearly ask a question that can be, I think, useful to many.

If we have colinear points on the convex hull, do we have to output all of them, or only the two extremities ?

I'm Using Gries and Stojmenovic version of Graham scan (as explained in Programming Challenges, p. 316), wich suppresses such points, and I don't manage to modify it in order to let them be in all the cases.
Could anyone help me please ? This is my first Convex Hull...

Thanks in advance !

[Julien Cornebise]

I finally got AC !
All colinear points should be present in the convex hull.
I finally used Graham's algorithm, just as mentionned above, and then added a piece of code to add ignored colinear points, because modifying the basis algorithm to include colinear points revealed to be a real pain.

But if anybody has another idea (I'm sure there's much better things to do, I'm not as good as I'd like to be), please say !!!

[titid_gede]

hi,

i want to ask, what is the output for this :

Code: Select all

3
1 1
2 2
3 3
0

thanks before.

[Julien Cornebise]

Hi.

For

Code: Select all

3
1 1
2 2
3 3
0

my AC prog answers :

Code: Select all

Region #1:
(1.0,1.0)-(2.0,2.0)-(3.0,3.0)-(1.0,1.0)
Perimeter length = 5.66