218 - Moth Eradication

[cantisan]

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

[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

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

[..]

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
 

[Jan]

I have getting WA on problem 218.

Can someone give me some test cases??

Thanks in advance.

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

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

[Jan]

Thanks someone2. I got it Accepted.

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

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

[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];
}

[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 ) ;		
	}
}

[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

[snar]

OK,
I'll let you know about results.

[Moha]

There was some threads on this topic like:
http://online-judge.uva.es/board/viewt ... light=218
try them!