Moderator: Board moderators

cantisan
New poster
Posts: 1
Joined: Thu Nov 13, 2003 3:47 am

### Can you please send me the code to solve Moth Eradication ?

Can you please send me the code to solve Moth Eradication ?

deragun
New poster
Posts: 1
Joined: Sun Mar 21, 2004 7:13 am

### 218

I programmed a solution in Java and then found out that the Collections Framework isn't supported, so I redid it in C++. Now it is saying that my output is exceeding the limit. I says this even if I have the program only output the Region # line for each set. If someone could help me understand what is causing this I would appreciate it.

[cpp]/* @JUDGE_ID: 43982PR 218 C++*/
#include <cstdio>
#include <vector>
#include <cmath>
#include <iomanip>
#include <iostream>

using namespace std;

void sortPoints(int, int, double[][2]);
void updateUpperPath(int, vector<int>&, double[][2]);
void updateLowerPath(int, vector<int>&, double[][2]);

int main() {
int curNum = 1;
int numPoints;
cin >> numPoints;
while (numPoints != 0) {
double thePoints[100][2];
for (int i = 0; i < numPoints; i++) {
cin >> thePoints[0];
cin >> thePoints[1];
}
cout << "Region #" << curNum << ":";
sortPoints(0, numPoints - 1, thePoints);
vector<int> upperPath, lowerPath;
if(numPoints != 1) {
upperPath.push_back(1);
upperPath.push_back(0);
lowerPath.push_back(1);
lowerPath.push_back(0);
for (int j = 2; j < numPoints; j++) {
upperPath.insert(upperPath.begin(),j);
lowerPath.insert(lowerPath.begin(),j);
updateUpperPath(numPoints,upperPath,thePoints);
updateLowerPath(numPoints,lowerPath,thePoints);
}
}
else {
upperPath.push_back(0);
lowerPath.push_back(0);
}
double totalLength = 0.0;
int upsize = upperPath.size();
int lowsize = lowerPath.size();
for (int d = 0; d < upsize; d++) {
cout << "(" << setiosflags(ios::fixed | ios::showpoint)
<< setprecision(1) << thePoints[upperPath[upsize - d - 1]][0] << "," <<
thePoints[upperPath[upsize - d - 1]][1];
if(upsize != 1) cout << ")-";
else cout << ")\n";
if (d > 0)
totalLength += sqrt(pow(thePoints[upperPath[upsize - d - 1]][0] -
thePoints[upperPath[upsize - d]][0], 2.0) +
pow(thePoints[upperPath[upsize - d - 1]][1] -
thePoints[upperPath[upsize - d]][1], 2.0));
}
for (int e = 1; e < lowsize; e++) {
if (e == lowsize - 1) {
cout << "(" << setiosflags(ios::fixed | ios::showpoint)
<< setprecision(1) << thePoints[lowerPath[e]][0] << "," <<
thePoints[lowerPath[e]][1] << ")\n";
}
else {
cout << "(" << setiosflags(ios::fixed | ios::showpoint)
<< setprecision(1) << thePoints[lowerPath[e]][0] << "," <<
thePoints[lowerPath[e]][1] << ")-";
}
if(numPoints > 2)totalLength += sqrt(pow(thePoints[lowerPath[e]][0] -
thePoints[lowerPath[e - 1]][0], 2.0) +
pow(thePoints[lowerPath[e]][1] -
thePoints[lowerPath[e - 1]][1], 2.0));
}
cout << "Perimeter length = " << setprecision(2) <<
setiosflags(ios::fixed | ios::showpoint) << totalLength << "\n\n";
curNum++;
cin >> numPoints;
}
return 0;
}

void sortPoints(int start, int end, double thePoints[][2]) {
if(end - start <= 0) return;
int half = (end-start)/2+start, newStart = (end-start)/2+start+1;
sortPoints(start,half,thePoints);
sortPoints(newStart,end,thePoints);
double temp[100][2];
int first = start, second = newStart, i = 0;
while(first <= half && second <= end) {
if(thePoints[first][0] <= thePoints[second][0]) {
temp[0] = thePoints[first][0];
temp[1] = thePoints[first][1];
first++;
}
else {
temp[0] = thePoints[second][0];
temp[1] = thePoints[second][1];
second++;
}
i++;
}
if(first > half) {
while(second <= end) {
temp[0] = thePoints[second][0];
temp[1] = thePoints[second][1];
second++;
i++;
}
}
else {
while(first <= half) {
temp[0] = thePoints[first][0];
temp[1] = thePoints[first][1];
first++;
i++;
}
}
i = 0;
for(int n = start; n <= end; n++) {
thePoints[n][0] = temp[i][0];
thePoints[n][1] = temp[i][1];
i++;
}
}

void updateUpperPath(int numPoints, vector<int>& upperPath, double thePoints[][2]) {
for(int m = 0; m < upperPath.size()-2; m++) {
if( thePoints[upperPath[m]][0] *
(thePoints[upperPath[m+1]][1] - thePoints[upperPath[m+2]][1]) -
thePoints[upperPath[m]][1] *
(thePoints[upperPath[m+1]][0] - thePoints[upperPath[m+2]][0]) +
thePoints[upperPath[m+1]][0] * thePoints[upperPath[m+2]][1] -
thePoints[upperPath[m+1]][1] * thePoints[upperPath[m+2]][0] <= 0) {
upperPath.erase(upperPath.begin() + (m+1));
m--;
}
else
return;
}
}

void updateLowerPath(int numPoints, vector<int>& lowerPath, double thePoints[][2]) {
for(int m = 0; m < lowerPath.size()-2; m++) {
if( thePoints[lowerPath[m]][0] *
(thePoints[lowerPath[m+1]][1] - thePoints[lowerPath[m+2]][1]) -
thePoints[lowerPath[m]][1] *
(thePoints[lowerPath[m+1]][0] - thePoints[lowerPath[m+2]][0]) +
thePoints[lowerPath[m+1]][0] * thePoints[lowerPath[m+2]][1] -
thePoints[lowerPath[m+1]][1] * thePoints[lowerPath[m+2]][0] >= 0) {
lowerPath.erase(lowerPath.begin() + (m+1));
m--;
}
else
return;
}
}[/cpp]

Thanks

zhenh
New poster
Posts: 10
Joined: Mon Oct 18, 2004 3:52 pm

### 218-Moth Eradication - Some tricky cases?

Code: Select all

``````#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct
{
float x;
float y;
float theta;
}point;

int compare( const void *arg1, const void *arg2 );
int cw( point *p1, point *p2, point *p );
float theta( point *p1, point *p2 );
float fabs( float x );
int graham( void );
float dist( point *p1, point *p2 );

int npts=0;
point pts[2000];
using namespace std;
int main( int argc, char *argv[] )
{
int m;
int i;
point t;
int case_count=0;
float perimeter;

fscanf( stdin, "%d", &npts );
while ( npts > 0 )
{
for ( i=0;i<npts;i++ )
{
fscanf( stdin, "%f %f", &pts[i].x, &pts[i].y );
}
if ( npts > 2 )
{
m = 0;
for ( i=1;i<npts;i++ )
{
if ( pts[i].y < pts[m].y )
m = i;
else if ( pts[i].y == pts[m].y && pts[i].x < pts[m].x )
m = i;
}
t = pts[0];
pts[0] = pts[m];
pts[m] = t;
for ( i=1;i<npts;i++ )
pts[i].theta = theta( &pts[0], &pts[i] );
qsort( &pts[1], npts-1, sizeof(point), compare );
m = graham( );
} else { m=npts-1; }
perimeter = 0;
case_count++;
fprintf( stdout, "Region #%d:\n", case_count );
for ( i=m;i>=0;i-- )
{
if ( i != 0 )
perimeter += dist( &pts[i], &pts[i-1] );
fprintf( stdout, "(%.1f,%.1f)-", pts[i].x, pts[i].y );
}
fprintf( stdout, "(%.1f,%.1f)\n", pts[m].x, pts[m].y );
perimeter += dist( &pts[0], &pts[m] );
fprintf( stdout, "Perimeter length = %.2f\n\n", perimeter );
fscanf( stdin, "%d", &npts );
}
return 0;
}

int compare( const void *arg1, const void *arg2 )
{
point *p1, *p2;
p1 = (point*)arg1;
p2 = (point*)arg2;
if ( p1->theta < p2->theta )
return -1;
if ( p1->theta == p2->theta )
{
if ( dist( &pts[0], p1 ) < dist( &pts[0], p2 ) )
return -1;
else
return 1;
}
return 1;
}

float dist( point *p1, point *p2 )
{
return sqrt((p1->x-p2->x)*(p1->x-p2->x)+(p1->y-p2->y)*(p1->y-p2->y));
}

int cw( point *p1, point *p2, point *p )
{
float cross;
cross = (p2->x-p1->x)*(p->y-p1->y)-(p2->y-p1->y)*(p->x-p1->x);
if ( cross > 0 ) /* clock-wise */
return 1;
else if ( cross == 0 ) /* co-linear */
return 0;
else /* counter-clockwise */
return -1;
}

float fabs( float x )
{
if ( x < 0 )
return -x;
return x;
}

float theta( point *p1, point *p2 )
{
float dx,dy,ax,ay;
float t;
dx = p2->x-p1->x;
dy = p2->y-p1->y;
ax = fabs( dx );
ay = fabs( dy );
if ( ax == 0 && ay == 0 )
t = 0;
else
t = dy/(ax+ay);
if ( dx < 0 )
t = 2 - t;
else if ( dy < 0 )
t = 4 + t;
return t * 90.0f;
}

int graham( void )
{
int m=2;
int l=npts-1;
int i;
point t;
stack<point> ps;

for ( i=3;i<npts;i++ )
{
while( cw( &pts[m-1], &pts[m], &pts[i] )==-1 )
{
ps.push( pts[m] );
m = m - 1;
}
m = m + 1;
pts[m] = pts[i];
}
while ( !ps.empty( ) )
{
t = ps.top( );
ps.pop( );
if ( cw( &pts[m-1], &pts[m], &t )>=0 )
{
m = m + 1;
pts[m] = t;
}
else
{
pts[l] = t;
l = l - 1;
}
}
if ( cw( &pts[m-1], &pts[0], &pts[m] ) == 1 )
m = m-1;
return m;
}
``````
The above code passes all the test cases I have got,
but always got WA from the judge.
Is it because some special cases? Or there is something else....?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
2 things:
1. don't use float, use double
2. the problem data is sensitive to precision error, write something like:

Code: Select all

``````   if ( cross > 1e-8 ) /* clock-wise */
return 1;
else if ( cross < -1e-8 ) /* counterclockwise */
return -1;
else
return 0
``````
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

I have getting WA on problem 218.

Can someone give me some test cases??

Ami ekhono shopno dekhi...
HomePage

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
There are plenty of test cases already.
Check out the i/o by Yarin.
Also, if you are still geting WA, it is probably your convex hull algorithm.
If it isn't that then it's your output function.
I used Graham scan , doubles and set EPSILON = 1e-6.

someone2
New poster
Posts: 10
Joined: Tue Jul 05, 2005 5:22 pm
Did you try this

Code: Select all

``````9
1 -1
1 0
1 1
0 1
0 -1
0 0
-1 1
-1 -1
-1 0
``````
This should give a perimeter length of 8.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Thanks someone2. I got it Accepted.
Ami ekhono shopno dekhi...
HomePage

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
There's no need to get fancy here, and there are no tricky cases. This problem should be solved easily with prewritten codes. If your convex hull code can output in clockwise order including the collinear points, then it should get AC. Otherwise, consider rewriting the convex hull code, there's probably something wrong with the convex hull code.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
Try changing this line:

Code: Select all

``if (surf(c[k-1], c[k], a[i]) != 1)``
to

Code: Select all

``if (surf(c[k-1], c[k], a[i]) == -1)``
You're not handling collinear points properly.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Hi, fellows!

I apologise for commencing a new discussion on "Moth Eradication" seeing that a great deal was said on it as it is, but I do hope that if supported by you it will be of considerable value for most of us. I've already read all that was written here ever since 2001, my code successfully passes all tricky cases which are present here, but invariably gets WA by the Judge....
If you construct a test case in which my code fails, I'd be grateful very much, as I myself have already tried all the cases I could think of
Come to my assistance, please, and let's make this stuff acceptable

Code: Select all

``````/#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define Epsilon 1e-6
#define N 1003

typedef
struct point{
double x;
double y;
}point;

typedef
struct vertice{
double ang;
double d;
double x;
double y;
}vertice;

point p[N];
point S[N];
int top;
vertice *v;

int compare_points1(const void *a, const void *b);
int compare_points2(const void *a, const void *b);
int compare_vertices1(const void *a,const void *b);
int compare_vertices2(const void *a,const void *b);

double distance(point *A, point *B);
int is_left_turn(point *p1,point *p2,point *p3);

void Graham_Scan_left(int k);
void Graham_Scan_right(int k);
void init();
void push(point A);
void pop();
void get_top(point *A);
void next_to_top(point *A);

point southpole,northpole;
point contour[N];
int j;

int main()
{
int n;
int t,k;
int test=0;
double Perimeter;
FILE *in=freopen("218.in","r",stdin);
scanf("%d",&n);
while(n)
{
for(t=0;t<n;t++)
scanf("%lf %lf",&p[t].x,&p[t].y);

qsort(p,n,sizeof(point),compare_points2);
northpole=p[0];

qsort(p,n,sizeof(point),compare_points1);
southpole=p[0];

v=malloc((n+1)*sizeof(vertice));
for(t=0;t<n-1;t++)
{
v[t].x=p[t+1].x;
v[t].y=p[t+1].y;
v[t].d=distance(&p[0],&p[t+1]);
v[t].ang=(v[t].x-p[0].x)/v[t].d;
}
qsort(v,n-1,sizeof(vertice),compare_vertices1);
for(t=0;t<n-1;t++)
{
p[t+1].x=v[t].x;
p[t+1].y=v[t].y;
}
for(t=0;t<n;t++)
if(fabs(p[t].x-northpole.x)<Epsilon && fabs(p[t].y-northpole.y)<Epsilon)
{
k=t;
break;
}
Graham_Scan_left(k);
printf("Region #%d:\n",++test);
for(t=top;t>=0;t--)
{
contour[top-t]=S[t];
}
j=top;
qsort(v,n-1,sizeof(vertice),compare_vertices2);
for(t=0;t<n-1;t++)
{
p[t+1].x=v[t].x;
p[t+1].y=v[t].y;
}
for(t=0;t<n;t++)
if(fabs(p[t].x-northpole.x)<Epsilon && fabs(p[t].y-northpole.y)<Epsilon)
{
k=t;
break;
}
Graham_Scan_right(k);
for(t=1;t<=top;t++)
{
contour[++j]=S[t];
}

for(t=0;t<j;t++)
printf("(%.1lf,%.1lf)-",contour[t].x,contour[t].y);
printf("(%.1lf,%.1lf)\n",contour[j].x,contour[j].y);
Perimeter=0;
for(t=0;t<j;t++)
Perimeter+=distance(&contour[t],&contour[t+1]);
printf("Perimeter length = %.2lf\n",Perimeter);

free(v);
scanf("%d",&n);
if(n)
printf("\n");
else
break;
}
return 0;
}

int compare_points1(const void *a, const void *b)
{
point *s=(point*)a;
point *t=(point*)b;

if(fabs(s->y-t->y)>Epsilon)
{
if(s->y<t->y)
return -1;
else
return 1;
}
else
{
if(fabs(s->x-t->x)>Epsilon)
{
if(s->x<t->x)
return -1;
else
return 1;
}
else
return 0;
}
}
int compare_points2(const void *a, const void *b)
{
point *s=(point*)a;
point *t=(point*)b;

if(fabs(s->y-t->y)>Epsilon)
{
if(s->y>t->y)
return -1;
else
return 1;
}
else
{
if(fabs(s->x-t->x)>Epsilon)
{
if(s->x>t->x)
return -1;
else
return 1;
}
else
return 0;
}
}
int compare_vertices1(const void *a,const void *b)
{
vertice *s=(vertice*)a;
vertice *t=(vertice*)b;

if(fabs(s->ang-t->ang)>Epsilon)
{
if(s->ang>t->ang)
return -1;
else
return 1;
}
else
{
if(fabs(s->d-t->d)>Epsilon)
{
if(s->d<t->d)
return -1;
else
return 1;
}
else
return 0;
}
}
int compare_vertices2(const void *a,const void *b)
{
vertice *s=(vertice*)a;
vertice *t=(vertice*)b;

if(fabs(s->ang-t->ang)>Epsilon)
{
if(s->ang<t->ang)
return -1;
else
return 1;
}
else
{
if(fabs(s->d-t->d)>Epsilon)
{
if(s->d<t->d)
return -1;
else
return 1;
}
else
return 0;
}
}
double distance(point *A, point *B)
{
double tmp1,tmp2;

tmp1=(A->x-B->x);
tmp2=(A->y-B->y);

return sqrt(tmp1*tmp1+tmp2*tmp2);
}
int is_left_turn(point *p1,point *p2,point *p3)
{
double tmp1,tmp2;

tmp1=(p2->x-p1->x)*(p3->y-p1->y);
tmp2=(p2->y-p1->y)*(p3->x-p1->x);

if(fabs(tmp1-tmp2)>Epsilon)
{
if(tmp1>tmp2)
return 1;
else
return 0;
}
else
return 1;
}
void Graham_Scan_left(int k)
{
int t;
point p1,p2;
init();
for(t=0;t<=((k>2)?(2):(k));t++)
push(p[t]);
for(t=3;t<=k;t++)
if(top>=1)
{
next_to_top(&p1);
get_top(&p2);
while(top>=2 && (!is_left_turn(&p1,&p2,&p[t])))
{
pop();
next_to_top(&p1);
get_top(&p2);
}
push(p[t]);
}
else
push(p[t]);
}

int is_right_turn(point *p1,point *p2,point *p3)
{
double tmp1,tmp2;

tmp1=(p2->x-p1->x)*(p3->y-p1->y);
tmp2=(p2->y-p1->y)*(p3->x-p1->x);

if(fabs(tmp1-tmp2)>Epsilon)
{
if(tmp1<tmp2)
return 1;
else
return 0;
}
else
return 1;
}

void Graham_Scan_right(int k)
{
int t;
point p1,p2;
init();
for(t=0;t<=((k>2)?(2):(k));t++)
push(p[t]);
for(t=3;t<=k;t++)
if(top>=1)
{
next_to_top(&p1);
get_top(&p2);
while(top>=2 && (!is_right_turn(&p1,&p2,&p[t])))
{
pop();
next_to_top(&p1);
get_top(&p2);
}
push(p[t]);
}
else
push(p[t]);
}
void init()
{
top=-1;
}
void push(point A)
{
top++;
S[top]=A;
}
void pop()
{
top--;
}
void next_to_top(point *A)
{
*A=S[top-1];
}
void get_top(point *A)
{
*A=S[top];
}``````

snar
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

### 218 - WA

Please, give me some test data for this problem.

Code: Select all

``````#include <stdio.h>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std ;
#define EPS 1e-7

struct P        { double x, y; P() {}; P( double q, double w ) : x( q ), y( w ) {}         };
P operator -    ( const P &p, const P &q ) { P u( p.x - q.x, p.y - q.y ); return u;  }
bool operator !=( const P &p, const P &q ) { return fabs(p.x - q.x)>EPS || fabs(p.y - q.y)>EPS;}

vector<P> JarvisMarch ( vector<P> Q )
{
vector<P> S ;
P p, q ;
int i, n ;
n = Q.size( ) ;
p = Q[0] ;
for ( i=1; i<n; i++ )
if ( Q[i].y < p.y-EPS )
p = Q[i] ;
else
if ( fabs( Q[i].y - p.y ) < EPS )
if ( Q[i].x < p.x-EPS )
p = Q[i] ;
do
{
S.push_back ( p ) ;
p = Q[0] ;
q = S.back( ) ;
for ( i=1; i<n; i++ )
p = ( Q[i] - q ).x * ( p - q ).y - ( Q[i] - q ).y * ( p - q ).x > EPS ||
( fabs(( Q[i] - q ).x * ( p - q ).y - ( Q[i] - q ).y * ( p - q ).x) < EPS && ( Q[i] - q ).x * ( Q[i] - q ).x + ( Q[i] - q ).y * ( Q[i] - q ).y >
( p - q ).x * ( p - q ).x + ( p - q ).y * ( p - q ).y+EPS ) ? Q[i] : p ;
}
while ( p != S[0] ) ;
return S ;
}

vector<P> Q ;

void main() {
P p ;
int n,it,i,j;
double perimeter ;
it=1;
while  ( scanf ( "%d", &n ),n ) {
Q.clear ( ) ;
for(i=0; i<n; i++) {
scanf("%lf%lf",&p.x,&p.y) ;
Q.push_back ( p ) ;
}

Q = JarvisMarch ( Q ) ;

n = Q.size ( ) ;

perimeter = 0.0 ;
for    ( i=n-1,j=0; j<n; i=j++ )
perimeter += sqrt ( (Q[i].x-Q[j].x)*(Q[i].x-Q[j].x) + (Q[i].y-Q[j].y)*(Q[i].y-Q[j].y) ) ;

printf ( "Region #%d:\n(%.1lf,%.1lf)", it++,Q[0].x+EPS,Q[0].y+EPS ) ;
for    ( i=n-1; i>=0; i-- ) printf ( "-(%.1lf,%.1lf)", Q[i].x+EPS, Q[i].y+EPS ) ;
putchar( '\n' ) ;
printf ( "Perimeter length = %.2lf\n\n", perimeter+EPS ) ;
}
}
``````
Narek Saribekyan

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Contact:
Try this input:

Code: Select all

``````8
0 0
.5 0
1 0
1 .5
1 1
.5 1
0 1
0 .5
0
``````
My Accepted code give this output:

Code: Select all

``````Region #1:
(0.0,1.0) - (0.5,1.0) - (1.0,1.0) - (1.0,0.5) - (1.0,0.0) - (0.5,0.0) - (0.0,0.0) - (0.0,1.0)
Perimeter length = 4.00
``````
hope it helps

snar
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia
OK,
I'll let you know about results.
Narek Saribekyan

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
There was some threads on this topic like:
http://online-judge.uva.es/board/viewt ... light=218
try them!