Page 3 of 5

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

Posted: Thu Nov 13, 2003 3:55 am
by cantisan
Can you please send me the code to solve Moth Eradication ?

218

Posted: Sun Mar 21, 2004 7:19 am
by deragun
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

218-Moth Eradication - Some tricky cases?

Posted: Thu Nov 11, 2004 3:01 pm
by zhenh

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....?

Posted: Sun Nov 28, 2004 7:20 pm
by ..
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
 

218 - Moth Eradication

Posted: Wed Jun 29, 2005 2:12 am
by Jan
I have getting WA on problem 218. :-?

Can someone give me some test cases??

Thanks in advance.

Posted: Fri Jul 22, 2005 10:51 pm
by daveon
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.

Posted: Sat Jul 23, 2005 1:18 pm
by someone2
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.

Posted: Wed Oct 19, 2005 12:34 am
by Jan
Thanks someone2. I got it Accepted. :D

Posted: Sun Feb 19, 2006 6:58 am
by sclo
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.

Posted: Sun Feb 19, 2006 7:02 am
by sclo
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.

218- Moth Eradication again...

Posted: Fri Mar 24, 2006 11:01 pm
by serur
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];
}

218 - WA

Posted: Tue May 09, 2006 7:10 pm
by snar
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 ) ;		
	}
}

Posted: Fri May 12, 2006 8:04 pm
by arif_pasha
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

Posted: Sat May 13, 2006 8:17 pm
by snar
OK,
I'll let you know about results.

Posted: Sat May 13, 2006 8:40 pm
by Moha
There was some threads on this topic like:
http://online-judge.uva.es/board/viewt ... light=218
try them!