811 - The Fortified Forest

[Miguel Angel]

Think my program is correct even though i always get WA. There are some details in redaction but i contemplate. Is there something i must do??

[Miguel Angel]

There's more than answer, they don't have a special program for multiple answer on that problem

[Adrian Kuegel]

You can write one and send it to problemset@acm.uva.es. That's what I do in these cases.
A sample judge is at http://acm.uva.es/contest/contest-judge-pascal.p. Other information is at http://acm.uva.es/problemset/info.html

[Nguyen Viet Bang]

Really disappointed and got stuck on this problem... I'm almost newbie here

I got Runtime error SIGSEGV . I've submitted a lot number of times , try to put many traps for array bounds checking . Also write a program to generate large data test...

Handle with real numbers very carefully

But my prog always runs smoothly in my comp , and runtime error (collapse very soon , 0:00.002 s) in UVA

Is there any possibility ??? You plz have a look at mine (quite messy since I 've modified it many times )

[cpp]#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<math.h>
#include<iomanip>

using namespace std ;

//#define DEBUG

#define M 20
#define INF 1000000000

const double EPSI = 1e-10 , PI = 3.14159 ;

struct Point
{
double x, y , len ;
int value , index;
} ;

int n , minValue , size , minChosen ;
int forestNo = 1 ;
double lSpare;
int lMark[M] , mark[M] , invalid[M] ;
double fAngle[M] , fDis[M];
Point p[M] , tP[M] = {0};

void swapP (Point& a , Point& b)
{
Point temp ;
temp = a; a = b ; b = temp ;
}

void readInput()
{
int i , j;
for (i = 0 ; i < n ; i ++ )
{
cin >> p[i].x >> p[i].y >> p[i].value >> p[i].len ;
p[i].index = i+1 ;
}

for (i = 0 ; i < n ; i++)
for (j = i+1 ; j < n ; j++)
if (p[i].value < p[j].value) swapP(p[i] , p[j]) ;
}

int equals(double a , double b)
{
return ( fabs(a - b) < EPSI) ;
}

/***** debug ****/
int out(int i)
{
if (i < 0 || i > M) return 1;
else return 0 ;
}

void findMinPoint()
{
size = 0 ;
int i ;

for (i = 0 ; i < n ; i++)
{
invalid[size] = 0 ;
if (mark[i] == 0) tP[size++] = p[i] ;
// debug
if ( out(i) || out(size)) cout<< "Error 68 " ;

}
// eliminate the coincide points
/*
for (i = 0; i < size ; i++)
for (j = i+1 ; j < size ; j ++ )
if (equals(tP[i].x , tP[j].x) && equals(tP[i].y , tP[j].y) ) invalid[j] = 1 ;
*/
for (i = 1; i < size ; i++)
{
//debug
if ( out(i)) cout<<" Error 81 " ;
if (tP[i].y < tP[0].y || (equals(tP[i].y , tP[0].y) && tP[i].x > tP[0].x) )
swapP(tP[i] , tP[0]) ;
else
if ( equals(tP[0].x , tP[i].x) && equals(tP[0].y , tP[i].y) )
{
//debug
if ( out(size-1)) cout<<" Error 88 " ;
swapP(tP[size-1] , tP[i]) ;
size-- ;
}
}
}

int countP()
{
int count = size,i;
for (i = 0 ; i < size ; i++)
{
#ifdef DEBUG
if ( out(i) ) cout<<"error 108" ;
#endif
count -= invalid[i] ;

}
return count ;
}

double angle(Point a , Point b)
{
// a is the lowest - right point
if (equals(a.y , b.y)) return 180 ;
if (equals(a.x , b.x)) return 90 ;
return ( atan( (b.y - a.y) / (b.x - a.x) ) / PI ) * 180 ;
}

void swapR (double& a , double& b)
{
double tam = a ; a =b ; b = tam;
}

void qSort(int l,int r)
{
double mid = fAngle[(l+r) / 2] , dmid = fDis[(l+r)/2] ;

int i = l, j=r;
do
{
while (fAngle[i] < mid || (equals(fAngle[i],mid) && fDis[i]<dmid))
{
/**** debug ****/
#ifdef DEBUG
if (out(i)) cout<< "error 142 " ;
#endif
i++ ;
}
while (fAngle[j] > mid || (equals(fAngle[j],mid) && fDis[j]>dmid))
{
/**** debug ****/
#ifdef DEBUG
if (out(j)) cout<< "error 148 " ;
#endif
j-- ;
}
if (i <= j)
{
swapP(tP[i] ,tP[j]) ;
swapR(fAngle[i] , fAngle[j]);
swapR(fDis[i] , fDis[j]) ;
i++;j-- ;
}
}
while (i <= j) ;
if (l < j) qSort(l,j) ;
if (i < r) qSort(i,r) ;
}

void bSort(int l , int r)
{
int i ,j ;
for (i = l ; i <= r ;i++)
for (j = i+1 ; j <= r ; j++)
if ( fAngle[i] > fAngle[j] ||
(equals(fAngle[i],fAngle[j]) && fDis[i]>fDis[j]) )
{
swapP(tP[i] , tP[j]) ;
swapR(fAngle[i] , fAngle[j]) ;
swapR(fDis[i] , fDis[j]) ;
}
}

double distance (Point a , Point b)
{
return sqrt ( (a.x-b.x)*(a.x-b.x) + (a.y - b.y)*(a.y - b.y) ) ;
}

void sortPoint()
{

int i ;
for (i = 1 ; i < size ; i++)
{
/**** debug ****/
#ifdef DEBUG
if (out(i)) cout<< "error 190 " ;
#endif DEBUG

fAngle[i] = angle(tP[0] , tP[i]) ;
fDis[i] = distance(tP[0] , tP[i]);
}
qSort(1,size-1) ;
for (i = 1 ; i < size ; i++)
{
/**** debug ****/
#ifdef DEBUG
if (out(i)) cout<< "error 199 " ;
if (out(i-1)) cout<< "error 200" ;
#endif
if (equals(tP[i].x , tP[i-1].x) && equals(tP[i].y , tP[i-1].y)) invalid[i] =1 ;
}

}


int next(int i)
{
i++ ;
if (i == size) i = 0 ;
while (invalid[i])
{
i++ ;
if (i == size) i = 0 ;
}
return i ;
}

int prev(int i)
{
i-- ;
if (i == -1) i = size-1 ;
while (invalid[i])
{
i-- ;
if (i == -1) i = size-1 ;
}
return i ;
}

int clockOK(int p1 , int p2 , int p3)
{
double a = (tP[p2].y - tP[p1].y) * (tP[p2].x + tP[p1].x)
+ (tP[p3].y - tP[p2].y) * (tP[p3].x + tP[p2].x)
+ (tP[p1].y - tP[p3].y) * (tP[p1].x + tP[p3].x) ;
return (a > 0) || equals(a,0) ;
}

double convexHullLength ()
{
int i ;

findMinPoint() ;

for (i = 0;i <size ; i++)
{
invalid[i] = 0;
#ifdef DEBUG
if ( out(i) ) cout<<" Error 256 " ;
#endif
}

sortPoint () ; // filter colinear points as well
if ( countP() <= 1) return 0 ;
if (countP() == 2) return 2*distance(tP[0] , tP[1]) ;

int p1 , p2 , p3 ;
p1 = 0 ;
p2 = next(p1);
p3 = next(p2) ;

do
{
/**** debug ****/
#ifdef DEBUG
if (out(p1) ) cout<< "error 258" ;
if (out(p2) ) cout<< "error 259" ;
if (out(p3) ) cout<< "error 260" ;
#endif

if (clockOK (p1,p2,p3))
{
p1 = p2 ; p2 = p3 ; p3 = next(p3) ;
}
else
{
invalid[p2] = 1 ;
p2 = p1 ; p1 = prev(p1) ;
}
}
while (p2 != 0);
p1 = 0;

double sum = 0;
do
{
#ifdef DEBUG
if ( out(p1) || out(next(p1)) ) cout<< "Error 249 " ;
#endif
sum += distance(tP[p1] , tP[next(p1)]) ;
p1 = next(p1) ;
} while (p1 != 0) ;
return sum ;
}

int canEnclose( double length , double& lSpare)
{
double l = convexHullLength () ;
if (l < length || equals(l,length))
{
lSpare = length - l ;
return 1;
}
return 0;
}

void tryTree (int i , int chosen , int fvalue , double length)
{
// is it ?
int d;
double lS ;
if (fvalue > minValue) return ;

if (i == n || chosen == n-1)
{
if (fvalue < minValue || ( fvalue == minValue && chosen < minChosen) )
if (canEnclose(length , lS))
{
minValue = fvalue ;
minChosen = chosen ;
for (d = 0 ; d < n ; d++)
{
//debug
#ifdef DEBUG
if (out(d)) cout<<"Error 283" ;
#endif
lMark[d] = mark[d] ;
}
lSpare = lS ;
}
return ;
}
int j ;
for (j=0; j < 2;j++)
{
mark[i] = j ;
tryTree(i+1 , chosen + mark[i] , (fvalue + mark[i]*p[i].value) , length+(mark[i]*p[i].len) ) ;
mark[i] = 0 ;
}
}

void process()
{
minValue = INF; minChosen = n+1 ;
int i ;
for (i = 0 ; i < n ; i++) mark[i] = 0 ;
tryTree (0 , 0 , 0 , 0) ;
}

void output()
{
cout <<"Forest "<<forestNo++<<endl ;
cout <<"Cut these trees:" ;

int i ;
for (i = 0 ; i < n ; i++) mark[i] = 0 ;
for (i = 0 ; i < n ; i++)
if (lMark[i]==1) mark[p[i].index-1] = 1 ;
for (i = 0 ; i < n ; i++)
if (mark[i] == 1) cout<<" "<<i+1;

cout<<endl ;
cout.setf(ios::fixed) ;
cout<<setprecision(2)<<"Extra wood: "<<lSpare<<endl ;
}

int main ()
{
//freopen("811.in" ,"r" , stdin) ;
//freopen("811.out" ,"w" , stdout) ;

bool first = true;
int k , noTest ;

cin>>noTest;


for (k = 0; k <noTest; k++)
{
cin>>n ;
{
if (n==0) break ;

readInput() ;
process() ;
if (first) first = false ;
else cout<<endl ;
output() ;
}
}
return 0 ;
}[/cpp]

[Larry]

Can someone post input/output for this? I get WA..

[Sanny]

What will be the output in cases where multiple "minimum-value and smallest number of trees" subset exists? This program doesn't have a multiple corrector.

The idea of this problem is simple I think - try all possible subsets and see whether you can do with this subset finding convex hull etc...


Regards
Sanny

[little joey]

The obvious, and somewhat disappointing answer would be that there are no such cases in the input. My program picks the first best answer it finds and outputs it. I might be lucky to always pick the right one, but since there are so many ACs, I think all answers are unique.

Have you seen the other thread on this problem? Some years ago the subject was mentioned, but there seem to be no actions taken.

[Sanny]

Then there may be some mistakes in my code. Let me find it....
Thanks anyway for the reply.

Regards
Sanny

[Sanny]

OK I've found my mistake in convex hull code and got AC after fixing it. And I also have taken first best answer.

Regards
Sanny

[lkfstephen]

Can anyone give me some sample input and output of this question?

I have so many WA on this question.

[lkfstephen]

Finally, I got AC.

I have some mistake in comparison.

[caffeine]

dont print two linebreaks on the last testcase, you will not get it accepted
took me like 20 WA to find out ...