1.

package acm_811_the_fortified_forest;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * FWP, AusgewŠhlte Probleme aus dem ACM Programming Contest, SS10
 * Problem: acm_811_the_fortified_forest
 * Link:
 *
 * @author Martin Lambeck
 * @version 1.0, 02.10.2010
 *
 * Method: graham scan, bruteforce
 * Status: Accepted
 * Runtime: 1.072
 */


public class Main
{
    static Scanner sc = new Scanner(System.in);
    static ArrayList<Tree> trees = new ArrayList<Tree>(16);
    static ArrayList<Tree> trs = new ArrayList<Tree>(16);
    static int tcase = 0;
    static int n = -1;
    static int bestCut = -1, bestVal = -1;
    static double bestWood = -1;
    static String bestConf;

    public static void main(String... args)
    {
        while (testcase());
    }
   
    public static double dist(Tree f, Tree t)
    {
        return Math.hypot(t.x - f.x, t.y - f.y);
    }

    public static boolean testcase()
    {
        trees.clear();
        n = sc.nextInt();

        if (n == 0)
            return false;

        for (int i = 0; i < n; i++)
        {
            trees.add(new Tree(i, sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }

        bestCut = Integer.MAX_VALUE;
        bestVal = Integer.MAX_VALUE;
        bestWood = -1.0;


        bt(0, 0, 0);

        if (tcase >= 1)
            System.out.print("\n");
       
        System.out.printf(
                "Forest %d\nCut these trees:%s\nExtra wood: %.2f\n", ++tcase,
                bestConf, Math.abs(bestWood));

        return true;
    }

    static double hull()
    {
        trs.clear();
       
        // trees that are considered in this case, add to trs
        for (int i = 0; i < trees.size(); i++)
            if (!trees.get(i).cut)
                trs.add(trees.get(i));
       
        int m = trs.size();

        // find root for graham scan (lowest y-value, lowest x-value among them on tie)
        Tree root = trs.get(0);

        for (Tree t : trs)
            if ((t.y < root.y) || ((t.y == root.y) && (t.x < root.x)))
                root = t;

        // assign precalculated angle and dist, in respect to the chosen root
        for (int i = 0; i < m; i++)
        {
            trs.get(i).angle = angle(root, trs.get(i));
            trs.get(i).dist = dist(root, trs.get(i));
        }

        // sort by angle ascending (on tie sort by dist ascending)
        Collections.sort(trs);
       
        //remove any other points laying on the root
        for (int i = 0; i < trs.size();)
            if ((trs.get(i).y == root.y) && (trs.get(i).x == root.x) && (trs.get(i) != root))
                trs.remove(i);
            else
                i++;
       
        //if there are two points with same angle, remove the one with lower distance
        for (int i = 2; i < trs.size();)
            if (trs.get(i).angle == trs.get(i-1).angle)
                trs.remove(i-1);
            else
                i++;
       
        if (trs.get(0) != root) //assert this...
            throw new NullPointerException();
       
        m = trs.size();
       
        // trivial cases n=1, n=2
        if (m == 1)
            return 0;

        if (m == 2)
            return 2.0 * dist(trs.get(0), trs.get(1));

        // stack, contains the hull
        LinkedList<Tree> st = new LinkedList<Tree>();

        st.addLast(trs.get(0));
        st.addLast(trs.get(1));
        st.addLast(trs.get(2));

        for (int i = 3; i < m; i++)
        {
            // if the last two nodes in the hull make a nonleft turn with the
            // current point
            // then remove last point from hull (then repeat this step)
            while (ccw(st.get(st.size() - 2), st.getLast(), trs.get(i)) <= 0)
                st.removeLast();

            // add to hull
            st.addLast(trs.get(i));
        }

        //total length of the fence
        double len = dist(st.getLast(), st.getFirst());
       
        while (st.size() > 1)
        {
            len += dist(st.getFirst(), st.get(1));
            st.removeFirst();
        }

        return len;
    }

    static void bt(int l, int cutVal, int cutWood)
    {
        if (cutVal > bestVal) //already found a better solution
            return;

        double fence = hull(); // length of fence

        if ((fence - 0.0000001) <= cutWood)
        {
            update(fence); // check to update solution

        } else if (l < n)
        {
            bt(l + 1, cutVal, cutWood); // next step, WITH tree

            Tree cut = trees.get(l);

            cut.cut = true;

            bt(l + 1, cutVal + cut.value, cutWood + cut.wood); // and W/O tree

            cut.cut = false;
        }

    }

    //update the solution
    static void update(double fence)
    {
        int cutVal = 0;
        int cutWood = 0;
        int cut = 0;

        for (Tree t : trees)
            if (t.cut)
            {
                cutVal += t.value;
                cutWood += t.wood;
                cut++;
            }   

        if ((cutVal < bestVal) || ((cutVal == bestVal) && (cut < bestCut)))
        {
            bestVal = cutVal;
            bestWood = cutWood - fence;
            bestCut = cut;

            StringBuilder sb = new StringBuilder("");

            for (Tree t : trees)
                if (t.cut)
                {
                    sb.append(" ");
                    sb.append(t.index + 1);
                }

            bestConf = sb.toString();
        }
    }

    /**
     * from wikipedia: Three points are a counter-clockwise turn if ccw > 0,
     * clockwise if ccw < 0, and collinear if ccw = 0 because ccw is a
     * determinant that gives the signed area of the triangle formed by t1, t2,
     * and t3.
     */
    static long ccw(Tree t1, Tree t2, Tree t3)
    {
        return ((t2.x - t1.x)) * (t3.y - t1.y) - ((t2.y - t1.y)) * (t3.x - t1.x);
    }


    /**
     * see wikipedia: http://de.wikipedia.org/wiki/Polarwinkel
     * angle will be within: [0¡; 180¡[ = [0; PI[
     */
    static double angle(Tree f, Tree t)
    {
        long dx = t.x - f.x;
        long dy = t.y - f.y;
       
        if (dy < 0)
            throw new NullPointerException();
       
        return Math.acos(dx / Math.sqrt(dx*dx + dy*dy));
    }
}
   
class Tree implements Comparable<Tree>
{
    int index;
    long x, y;
    int value, wood;
    double angle = -1.0, dist = -1.0;
    boolean cut = false;

    public Tree(int ii, int xx, int yy, int v, int w)
    {
        index = ii;
        x = xx;
        y = yy;
        value = v;
        wood = w;
    }

    public int compareTo(Tree p)
    {
        if (angle < p.angle)
            return -1;

        if (angle > p.angle)
            return 1;

        if (dist < p.dist)
            return -1;

        if (dist > p.dist)
            return 1;

        return 0;
    }
}