Page 1 of 1

811 - The Fortified Forest

Posted: Tue Aug 13, 2002 2:43 am
by 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??

Re: 811 "The fortified forest" Is correct???

Posted: Thu Aug 15, 2002 2:38 am
by Miguel Angel
There's more than answer, they don't have a special program for multiple answer on that problem :evil:

Posted: Thu Aug 15, 2002 12:32 pm
by 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

811 - Got Runtime error SIGSEGV

Posted: Wed Feb 18, 2004 11:52 am
by 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.x >> p.y >> p.value >> p.len ;
p.index = i+1 ;
}

for (i = 0 ; i < n ; i++)
for (j = i+1 ; j < n ; j++)
if (p.value < p[j].value) swapP(p , 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 == 0) tP[size++] = p ;
// 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.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]

Posted: Wed Mar 10, 2004 1:51 pm
by Larry
Can someone post input/output for this? I get WA..

811 - The Fortified Forest Why no multiple corrector?

Posted: Mon Oct 10, 2005 4:52 pm
by 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

Posted: Mon Oct 10, 2005 5:12 pm
by 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.

Posted: Mon Oct 10, 2005 5:18 pm
by Sanny
Then there may be some mistakes in my code. Let me find it....
Thanks anyway for the reply.

Regards
Sanny

Posted: Mon Oct 10, 2005 6:13 pm
by 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

Posted: Sat Dec 24, 2005 12:37 pm
by lkfstephen
Can anyone give me some sample input and output of this question?

I have so many WA on this question.

Posted: Sat Dec 24, 2005 8:19 pm
by lkfstephen
Finally, I got AC.

I have some mistake in comparison.

Re: 811 - The Fortified Forest

Posted: Mon Oct 18, 2010 10:36 pm
by caffeine
dont print two linebreaks on the last testcase, you will not get it accepted
took me like 20 WA to find out ...

Re: 811 - The Fortified Forest

Posted: Mon Jun 08, 2015 2:36 pm
by safarisoul
I've got a lot of WA, can anyone help me find the problem?

Code: Select all

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int t = 1;; t++) {
            if (t > 1)
                System.out.println();
            int n = sc.nextInt();
            if (n == 0)
                break;
            Point[] trees = new Point[n];
            int[] vs = new int[n], ls = new int[n];
            for (int i = 0; i < n; i++) {
                trees[i] = new Point(sc.nextInt(), sc.nextInt());
                vs[i] = sc.nextInt();
                ls[i] = sc.nextInt();
            }
            int minv = Integer.MAX_VALUE, mincut = Integer.MAX_VALUE, sig = 0;
            double extra = 0;
            for (int mask = 0; mask < (1 << n); mask++) {
                int value = 0, len = 0, cut = Integer.bitCount(mask), k = 0;
                Point[] rest = new Point[n + 1];
                for (int i = 0; i < n; i++)
                    if ((mask & (1 << i)) > 0) {
                        value += vs[i];
                        len += ls[i];
                    }
                    else
                        rest[k++] = trees[i];
                double perimeter = perimeter(rest, k);
                if (len >= perimeter) {
                    if ((value < minv) || (value == minv && cut < mincut)) {
                        minv = value;
                        mincut = cut;
                        extra = len - perimeter;
                        sig = mask;
                    }
                }
            }
            System.out.println("Forest " + t);
            String cut = "";
            for (int i = 0; i < n; i++)
                if ((sig & (1 << i)) > 0)
                    cut += " " + (i + 1);
            System.out.println("Cut these trees:" + cut);
            System.out.printf("Extra wood: %.2f\n", extra);
        }
        sc.close();
    }

    public static double perimeter(Point[] ps, int n) {
        if (n == 0 || n == 1)
            return 0;
        int last = n - 1;
        if (n > 2) {
            Arrays.sort(ps, 0, n, Point.xyComparator);
            Point.origin = ps[0];
            Arrays.sort(ps, 1, n, Point.angleComparator);
            last = 1;
            for (int i = 2; i < n; i++) {
                while (last > 0 && ccw(ps[last - 1], ps[last], ps[i]) <= 0)
                    last--;
                ps[++last] = ps[i];            }
        }
        ps[++last] = ps[0];
        double sum = 0;
        for (int i = 0; i < last; i++)
            sum += Point.dis(ps[i], ps[i + 1]);
        return sum;
    }

    private static double ccw(Point p1, Point p2, Point p3) {
        return (p3.y - p1.y) * (p2.x - p1.x) - (p2.y - p1.y) * (p3.x - p1.x);
    }

}

class Point {
    public int x;
    public int y;

    public static Point origin;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public static double dis(Point p1, Point p2) {
        double xd = p1.x - p2.x, yd = p1.y - p2.y;
        return Math.sqrt(xd * xd + yd * yd);
    }

    public static Comparator<Point> xyComparator = new Comparator<Point>() {
        public int compare(Point p1, Point p2) {
            if (p1.y == p2.y)
                return Integer.compare(p1.x, p2.x);
            return Integer.compare(p1.y, p2.y);
        }
    };

    public static Comparator<Point> angleComparator = new Comparator<Point>() {
        public int compare(Point p1, Point p2) {
            if (p1.y == origin.y && p2.y == origin.y)
                return Integer.compare(p1.x, p2.x);
            return ccw(origin, p1, p2) > 0 ? -1 : 1;
        }
    };

    private static double ccw(Point p1, Point p2, Point p3) {
        return (p3.y - p1.y) * (p2.x - p1.x) - (p2.y - p1.y) * (p3.x - p1.x);
    }
}