811 - The Fortified Forest

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

Moderator: Board moderators

Post Reply
Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

811 - The Fortified Forest

Post by Miguel Angel » Tue Aug 13, 2002 2:43 am

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??
:D Miguel & Marina :D

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

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

Post by Miguel Angel » Thu Aug 15, 2002 2:38 am

There's more than answer, they don't have a special program for multiple answer on that problem :evil:
:D Miguel & Marina :D

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Aug 15, 2002 12:32 pm

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
New poster
Posts: 4
Joined: Tue Nov 04, 2003 8:06 pm

811 - Got Runtime error SIGSEGV

Post by Nguyen Viet Bang » Wed Feb 18, 2004 11:52 am

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]

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Mar 10, 2004 1:51 pm

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

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

811 - The Fortified Forest Why no multiple corrector?

Post by Sanny » Mon Oct 10, 2005 4:52 pm

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Oct 10, 2005 5:12 pm

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
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Mon Oct 10, 2005 5:18 pm

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

Regards
Sanny

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Mon Oct 10, 2005 6:13 pm

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
New poster
Posts: 2
Joined: Sat Dec 24, 2005 12:30 pm

Post by lkfstephen » Sat Dec 24, 2005 12:37 pm

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

I have so many WA on this question.

lkfstephen
New poster
Posts: 2
Joined: Sat Dec 24, 2005 12:30 pm

Post by lkfstephen » Sat Dec 24, 2005 8:19 pm

Finally, I got AC.

I have some mistake in comparison.

caffeine
New poster
Posts: 2
Joined: Sun Oct 10, 2010 2:49 pm

Re: 811 - The Fortified Forest

Post by caffeine » Mon Oct 18, 2010 10:36 pm

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

safarisoul
New poster
Posts: 1
Joined: Mon Jun 08, 2015 2:24 pm

Re: 811 - The Fortified Forest

Post by safarisoul » Mon Jun 08, 2015 2:36 pm

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);
    }
}
Last edited by brianfry713 on Fri Jun 19, 2015 6:37 am, edited 1 time in total.
Reason: Added code blocks

Post Reply

Return to “Volume 8 (800-899)”