218 - Moth Eradication

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

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 ?

Post by cantisan » Thu Nov 13, 2003 3:55 am

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

Post by deragun » Sun Mar 21, 2004 7:19 am

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?

Post by zhenh » Thu Nov 11, 2004 3:01 pm

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

Post by .. » Sun Nov 28, 2004 7:20 pm

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:
  • Please make discussion about the algorithm BRFORE posting source code.
    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
Location: Dhaka, Bangladesh
Contact:

218 - Moth Eradication

Post by Jan » Wed Jun 29, 2005 2:12 am

I have getting WA on problem 218. :-?

Can someone give me some test cases??

Thanks in advance.
Ami ekhono shopno dekhi...
HomePage

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Fri Jul 22, 2005 10:51 pm

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

Post by someone2 » Sat Jul 23, 2005 1:18 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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Oct 19, 2005 12:34 am

Thanks someone2. I got it Accepted. :D
Ami ekhono shopno dekhi...
HomePage

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Feb 19, 2006 6:58 am

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Feb 19, 2006 7:02 am

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

218- Moth Eradication again...

Post by serur » Fri Mar 24, 2006 11:01 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

Post by snar » Tue May 09, 2006 7:10 pm

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
Location: Dhaka , Bangladesh
Contact:

Post by arif_pasha » Fri May 12, 2006 8:04 pm

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

Post by snar » Sat May 13, 2006 8:17 pm

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:

Post by Moha » Sat May 13, 2006 8:40 pm

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

Post Reply

Return to “Volume 2 (200-299)”