## 11096 - Nails

Moderator: Board moderators

farzane
New poster
Posts: 26
Joined: Thu Jun 15, 2006 9:26 am

### 11096 - Nails

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

Code: Select all

``removed``
Last edited by farzane on Sun Sep 24, 2006 10:11 pm, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
.... edited
Last edited by helloneo on Fri Sep 28, 2007 6:41 pm, edited 1 time in total.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
New poster
Posts: 26
Joined: Thu Jun 15, 2006 9:26 am
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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I don't use int's.. and I've tried the n=0,1,2 cases.. are there any other particularly tricky cases?

sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm
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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
In the N = 2 case, say

1 2
0 1
0 2

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

H_Hima
New poster
Posts: 18
Joined: Mon Sep 25, 2006 10:56 am
Location: Solar System
Contact:

### why WA

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
So, no trick cases?

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Larry wrote: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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
You're welcomed!

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

H_Hima
New poster
Posts: 18
Joined: Mon Sep 25, 2006 10:56 am
Location: Solar System
Contact:

### pleeeeeeeease help me (WA)

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
New poster
Posts: 5
Joined: Thu Oct 19, 2006 5:21 pm
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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
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
New poster
Posts: 5
Joined: Thu Oct 19, 2006 5:21 pm
why

input

1 2
1 0
2 0

output

2.00000

??