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.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]

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 ...

[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);
    }
}