11096 - Nails

[farzane]

I'm getting WA.Where is my mistake?Is this problem convex hull?

Code: Select all

removed

Please help.Thanks in advance.

[helloneo]

.... edited

[little joey]

Addition and subtraction of ints can lead to overflow/underflow. Your code suffers from this, farzane, as did my first attempts during the contest.

[farzane]

Thank you very much little joey ,I ghanged all of int type in my code to long long and got AC. I haven't think about this kind of bug for this problem.
Thank you again very very much.

[Larry]

I don't use int's.. and I've tried the n=0,1,2 cases.. are there any other particularly tricky cases?

[sklitzz]

I'm having trouble with this task. I keep getting Runtime Error. Does anybody see the bug?

Code: Select all

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;

#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define SQ(x) (x)*(x)

#define INF INT_MAX / 2
#define x first
#define y second

long long N, M, L;
vector < pair < long long, long long > > t;

double dist( pair < long long, long long > &a, pair < long long, long long > &b ) {
	long long dx = a.x - b.x;
	long long dy = a.y - b.y;
	return sqrt( (double)(dx*dx + dy*dy) );
}

bool ccw( const pair < long long, long long > &a, const pair < long long, long long > &b, const pair < long long, long long > &c ) {
	long long x = a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y);
	return ( x > 0 );
}

bool cmp( const pair < long long, long long > &a, const pair < long long, long long > &b ) {
	return ccw( t[0], a, b );
}

long double convex() {
	
	long long min_x = INF, min_y = INF, koja = -1;
	for( int i = 0; i < t.size(); ++i )
		if( min_x > t[i].x || ( min_x == t[i].x && min_y > t[i].y ) ) {
		min_x = t[i].x; min_y = t[i].y;
		koja = i;
		}
	
		swap( t[0], t[koja] );
		sort( t.begin(), t.end(), cmp ); 
		t.pb( t[0] ); 
	

		vector < pair < long long, long long > > CH;
		CH.pb( t[0] ); 
		CH.pb( t[1] );
		for( int i = 2; i < t.size(); ++i ) {
			while( !ccw( CH[CH.size()-2], CH[CH.size()-1], t[i] ) )
				CH.pop_back();
			CH.pb( t[i] );
		}
	
		long double ret = 0.0;
		for( int i = 0; i < CH.size()-1; ++i )
			ret += dist( CH[i], CH[i+1] );
		return ret;	
}

int main() {
	scanf( "%d", &M ); 
	for( int i = 0; i < M; ++i ) {
		scanf( "%d %d", &L, &N ); t.resize( N );
 		for( int j = 0; j < N; ++j ) scanf( "%d %d", &t[j].x, &t[j].y );
		 
		long double rjesenje = convex();
		printf( "%.5llf\n", max( convex(), (long double)L ) );
	}
	
	return 0;
}

[Larry]

In the N = 2 case, say

1 2
0 1
0 2

are we suppose to print "2" or "1"? Thanks!

[H_Hima]

I don't understand at all what is my mistake.
please take some testcases that my code got wrong on them.

here is my code

Code: Select all

#include<cmath>
#include<stdio.h>
#include<iostream>
using namespace std;

long double P;

struct point {
	long long x,y;
	point& operator =(point &other) {	x=other.x;	y=other.y;	return (*this);	}
	bool operator ==(point &other)	{	
		if(x==other.x&&y==other.y)	return true;	
		return false;
	}
	bool operator != (point &other) {
		if((*this)==other)	return false;
		return true;
	}
	double operator-(point &other) {
		return (sqrt((long double)(x-other.x)*(x-other.x)+(y-other.y)*(y-other.y)));
	}
};

void main() {
	point points[100];
	bool node[100];
	P=acos(-1.0);
	long long i,j,t,num,step,min,best;
	long double Isize,Fsize,angel,mangel,cangel,dx,dy;
	point start,cur;
	cin>>t;
	while(t) {
		min=10000;
		cin>>Isize>>num;
		Fsize=0;
		for(i=0;i<num;i++) {
			cin>>points[i].x>>points[i].y;
			node[i]=true;
			for(j=0;j<i;j++) {
				if(points[j]==points[i]) {
					num--;
					i--;
					break;
				}
			}
			if(points[i].y<min||(!i)) {
				min=points[i].y;
				start=points[i];
				best=i;
			}
		}
		bool sw=true;
		cur=start;
		if(num==1)	Fsize=0;
		else {
			step=0;
			cangel=0;
			while(sw) {
				mangel=9;
				for(i=0;i<num;i++) {
					if(node[i]&&points[i]!=cur) {
						dx=points[i].x-cur.x;
						dy=points[i].y-cur.y;
						angel=atan2(dy,dx);
						if(angel<0)	angel+=(2*P);
						if(angel<=mangel) {
							if(angel==mangel&&(abs(dx)>abs((long double)(points[best].x-cur.x)))) {
								node[best]=false;
								best=i;
							}
							else if(angel==mangel)	node[i]=false;
							else {
								best=i;
								mangel=angel;
							}
						}
					}
				}
				node[best]=false;
				step++;
				Fsize+=(points[best]-cur);
				cangel=mangel;
				cur=points[best];
				if(cur==start)	sw=false;
			}
		}
		if(step==2)	Fsize/=2;
		if(Fsize<Isize)	printf("%.5lf\n",(long double)Isize);
		else			printf("%.5lf\n",Fsize);
		t--;
	}
}

thanks.

[Larry]

So, no trick cases?

[helloneo]

In the N = 2 case, say

1 2
0 1
0 2

are we suppose to print "2" or "1"? Thanks!

My AC code gives

Code: Select all

2.00000

Your test case helped me to get AC.. Thanks..

[Larry]

You're welcomed!

Unforunately, I still haven't AC'ed this. I probably need somethign more in depth!

[H_Hima]

Hi to everybody
there is anybody there to help me??

I use graham's covex skin to finding the convexhull and finding the perimeter from that.
But why WA.
this is my code

Code: Select all

Dear H_Hima:

You are trying to solve "Nails" (problem 11096).
I have received and stored your C++ program. It will be compiled and 
run
as soon as possible; please be patient waiting for the results...

--
The Online Judge

--------------- The program I'll compile begins here: ---------------
#include <cmath>
#include <cstdio>
#include <stdlib.h>
#include<iostream>
using namespace std;

const long double P=acos(-1.0);

struct point{
	long long x,y;
	long double ang;
	}a[110],b[110];

long double atan2(point a,point b) {
	if(a.x==b.x&&a.y==b.y)	return 0;
	long double ang=atan2((long double)b.y-a.y,b.x-a.x);
	if(ang<0)	ang+=2*P;
	return ang;
	}

int comp(const void *a,const void *b) {
	point A=*(point *)a,B=*(point *)b;
	if(A.ang>B.ang)	return 1;
	if(A.ang<B.ang)	return -1;
	return 0;
	}

long long convexhull(long long n) {
	long long i,count,m=-1;
	long double d1,d2;
	point temp;
	for(i=0;i<n;i++) {
		if(m==-1||a[m].y>a[i].y||(a[m].y==a[i].y&&a[m].x<a[i].x))
			m=i;
		}
	temp=a[m];
	a[m]=a[0];
	a[0]=temp;
	a[0].ang=0;
	a[n]=a[0];
	for(i=1;i<n;i++)
		a[i].ang=atan2(a[0],a[i]);
	qsort(a,n,sizeof(point),comp);
	count=1;
	b[0]=a[0];
	b[1]=a[1];
	if(n<3)	{
		b[n]=a[0];
		return n+1;
	}
	for(i=2;i<=n;i++) {
		count++;
		b[count]=a[i];
		d1=atan2(b[count-2],b[count-1]);
		d2=atan2(b[count-1],b[count]);
		while(d2&&d2<d1) {
			b[count-1]=b[count];
			count--;
			d1=atan2(b[count-2],b[count-1]);
			d2=atan2(b[count-1],b[count]);
			}
		}
	return count+1;
	}
void main() {
	long long i,t,init,n,count;
	long double len;
	cin>>t;
	while(t) {
		cin>>init>>n;
		for(i=0;i<n;i++)	cin>>a[i].x>>a[i].y;
		count=convexhull(n);
		len=0;
		for(i=1;i<count;i++)
			len+=sqrt((long 
double)(b[i-1].x-b[i].x)*(b[i-1].x-b[i].x)+(b[i-1].y-b[i].y)*(b[i-1].y-b[i].y));
		if(len<init)	len=init;
		printf("%.5lf\n",len);
		t--;
	}
}

thanks alot to everybody that decide to help me.

thanks

[AxM]

Hi
there is anybody to help me??

Some I/O ??

But why WA.
this is my code

Code: Select all

#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>


typedef struct
{
   long long x;
   long long y;
}Point;

Point point[101];
Point p0;
long stack[101];
long long ps;
long long i,a;
long long l,n;
long long x,y;
long double P;


int compare(const void *a, const void *b);
void Convex_Hull(long n);

int main(){
       


scanf("%lld",&a);

while(a>0){
a--;
    scanf("%lld %lld",&l,&n);
    for(i=0;i<n;i++)
                    scanf("%lld %lld",&point[i].x,&point[i].y);
   
    if(n>2){     
          qsort(point,n,sizeof(point[0]),compare);         
          Convex_Hull(n);
    P=0;
    x=point[stack[1]].x;
    y=point[stack[1]].y;
    for(i=2;i<ps;i++){
                   
                          P+=sqrt( (point[stack[i]].x-x)*(point[stack[i]].x-x) + (point[stack[i]].y-y)*(point[stack[i]].y-y) );
                          x=point[stack[i]].x;
                          y=point[stack[i]].y;         
                     }
    i=1;
    P+=sqrt( (point[stack[i]].x-x)*(point[stack[i]].x-x) + (point[stack[i]].y-y)*(point[stack[i]].y-y) );
                    }
    else
        {
        if(n==2)
                P=sqrt( (point[0].x-point[1].x)*(point[0].x-point[1].x) + (point[0].y-point[1].y)*(point[0].y-point[1].y) );             
        else
            P=0;
        }
       
                         
    if(P>l)
                printf("%.5llf\n",P);
    else
        printf("%lld.00000\n",l);
           
           
           
           
}

return 0;
}

long long cross_product(Point a, Point b, Point c)
{
   return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
}

int compare(const void *a, const void *b)
{
   long long k, d1, d2;

   Point *sp1 = (Point *)a;
   Point *sp2 = (Point *)b;

   k = cross_product(p0,*sp1,*sp2);
   if(k > 0)
      return -1;
   else if(k == 0)
   {
      d1 = (sp1->x - p0.x)*(sp1->x - p0.x) + (sp1->y - p0.y)*(sp1->y - p0.y);
      d2 = (sp2->x - p0.x)*(sp2->x - p0.x) + (sp2->y - p0.y)*(sp2->y - p0.y);

      if(d1 < d2)
         return -1;
      else
         return 1;
   }
   else
      return 1;
}


void Convex_Hull(long n)
{
   long long i;

   stack[1] = 0;
   stack[2] = 1;
   stack[3] = 2;
   ps = 3;
   for(i=2; i<n; ++i)
   {
      while(cross_product(point[stack[ps]], point[stack[ps-1]], point[i]) >= 0)
      {
         ps--;
         if(ps == 1)   break;
      }
      
      ps++;
      stack[ps] = i;
      
   }

   if(cross_product(point[stack[ps]], point[stack[ps-1]], point[stack[1]]) >= 0)
      ps--;

   stack[ps+1] = stack[1];
   ps++;

} 

[helloneo]

Try this case..

Code: Select all

2

1 2
1 0
2 0

1 3
1 0
2 0
3 0

My output is..

Code: Select all

2.00000
4.00000

Hope this helps..

[AxM]

why

input

1 2
1 0
2 0

output

2.00000

??